3.1.5. Example of Non-Optimal Colouring

Try these first

1. 1.

   Define vertex colouring in your own words.

   Hint

   Remember how colours relate to adjacency.

2. 2.

   What does the chromatic number represent?

   Hint

   Think about colouring requirements and their limits.

3. 3.

   What does vertex colouring ensure in a graph?

   • It ensures adjacent vertices can share the same colour
   • It ensures adjacent vertices have different colours
   • It ensures less than half the vertices are coloured

   Hint

   Think about the goal of preventing shared colours among adjacent nodes.

4. 4.

   Is the greedy algorithm guaranteed to produce an optimal colouring?

   • True
   • False

   Hint

   Reflect on how the order affects the results.

5. 5.

   Given a graph with specific vertices and edges, provide at least two different vertex sequences and demonstrate how each affects the chromatic number.

   Hint

   Try to visualize the graph and explore various configurations.

6. 6.

   Create a graph with a maximum degree of 3 and demonstrate the relationship between its chromatic number and its maximum degree.

   Hint

   Sketch out different valid colourings to support your finding.