3. Vertex and Edge Colouring

Try these first

1. 1.

   Define vertex colouring.

   Hint

   Think about scheduling.

2. 2.

   What is the goal of edge colouring?

   Hint

   Consider tournament matches.

3. 3.

   What is the vertex chromatic number?

   • The number of edges in a graph
   • The minimum number of colours needed to colour a graph
   • The maximum degree of a vertex

   Hint

   Think about preventing colour conflicts.

4. 4.

   True or False: The greedy algorithm guarantees an optimal solution for vertex colouring.

   • True
   • False

   Hint

   Consider the order in which you pick vertices.

5. 5.

   Given a complex graph with multiple vertices and edges, use the greedy algorithm to determine the chromatic number. Discuss whether the result is optimal.

   Hint

   Draw the graph and apply the algorithm step-by-step.

6. 6.

   Design a simple graph and explain how you would schedule a round-robin tournament using edge colouring. Calculate the edge chromatic number using the Gupta-Vizing theorem.

   Hint

   Visualize the tournament as a complete graph.