3.1.2. Vertex Colouring Problem

Try these first

1. 1.

   What is the vertex colouring problem?

   Hint

   Think of scheduling conflicts.

2. 2.

   Define chromatic number.

   Hint

   Remember how you schedule your subjects!

3. 3.

   What does vertex coloring aim to achieve?

   • Two adjacent vertices have the same color
   • No two adjacent vertices share the same color
   • Using as many colors as possible

   Hint

   Relate it back to exam scheduling.

4. 4.

   True or False: The chromatic number can be determined efficiently for all types of graphs.

   • True
   • False

   Hint

   Remember the challenges with large graphs.

5. 5.

   Create a graph with 5 vertices and describe how many colors you can use at minimum for a valid coloring. Justify your reasoning.

   Hint

   Draw different combinations to find a minimal color scheme.

6. 6.

   Using a graph of your choice, implement the greedy algorithm step-by-step to show the coloring process and explain the results. Discuss if the coloring is optimal.

   Hint

   Visual aids can assist in understanding the algorithm's application.