3.1.6. Upper Bound on Vertex Chromatic Number

Try these first

1. 1.

   What does vertex coloring involve?

   Hint

   Think about graph connections.

2. 2.

   What is the maximum degree Δ(G)?

   Hint

   Consider the vertex with the most connections.

3. 3.

   What is the vertex chromatic number of a graph?

   • The maximum number of edges
   • The minimum number of colors needed for coloring
   • The average of the degrees

   Hint

   Focus on the definition of chromatic number.

4. 4.

   True or False: The greedy algorithm can always give the optimal coloring.

   • True
   • False

   Hint

   Consider how order affects the results.

5. 5.

   Consider a graph of 6 vertices forming a cycle. Determine the chromatic number and explain your reasoning.

   Hint

   Visualize the sequence of colors placed around the cycle.

6. 6.

   Design a graph that can be colored optimally with 3 colors yet a greedy algorithm may suggest 4, and explain.

   Hint

   Investigate the edges connecting two groups.