3.1.4. Greedy Algorithm for Vertex Colouring

Try these first

1. 1.

   What is vertex colouring?

   Hint

   Think of it like arranging different subjects without conflicts.

2. 2.

   What does the chromatic number represent?

   Hint

   It's a specific quantity related to the graph's vertices.

3. 3.

   What does vertex colouring aim to achieve?

   • Minimize the number of colours
   • Maximize the number of colours
   • No relation to colours

   Hint

   Remember what you aim to achieve with colour assignments.

4. 4.

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

   • True
   • False

   Hint

   Reflect on what happens if you choose the wrong vertex first.

5. 5.

   Given a graph where vertex degrees vary, design a strategy for colour assignment that minimizes overlaps, and analyze its effectiveness.

   Hint

   Consider how high-degree vertices limit your colour options.

6. 6.

   Suppose you have a complete graph with ten vertices. How many colours must you use, and why? Can you relate this to chromatic number?

   Hint

   Recall how complete graphs are structured.