3.1.1. Vertex Colouring Motivation

Try these first

1. 1.

   Define vertex colouring in the context of graph theory.

   Hint

   Think about adjacent vertices.

2. 2.

   What does the vertex chromatic number represent?

   Hint

   Consider what the minimum means.

3. 3.

   What is vertex colouring?

   • Assigning colors to edges in a graph
   • The process of assigning colors to vertices in a graph
   • The number of colors in a graph

   Hint

   Think about where colors are assigned.

4. 4.

   True or False: The vertex chromatic number is always equal to the number of vertices in the graph.

   • True
   • False

   Hint

   Consider when you might need fewer colors.

5. 5.

   Given a graph with 12 vertices and a maximum degree of 6, create a set of vertex color assignments that achieves optimal colouring for a scheduling scenario.

   Hint

   Start from the highest degree vertices down.

6. 6.

   Demonstrate a scenario in which the greedy coloring algorithm fails to produce an optimal number of colors. Construct a small graph example for clarity.

   Hint

   Think about conflicting edges.