For every graph G, show that there is an ordering of the vertices of G such that the numberof required colors from Greedy Algorithm is exactly χ(G). (You should describe how togive such an order.)

문제출처

광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 9

---

Solution

1. Assume that the graph $G$ can be properly colored with exactly $\chi(G)$ colors.

• Remember that each color class forms an independent set.

2. Using this proper coloring, define the vertex order as follows:
a. List all vertices in the color class corresponding to color 1.
b. Next, list all vertices in the color class corresponding to color 2.
c. Continue this process until all vertices in the color class corresponding to color $\chi(G)$ are listed.

3. Apply the Greedy Coloring algorithm in the given order.

4. For each vertex:

• Assign the smallest available color that has not been used by its neighbors (already colored vertices).

5. Following the given order ensures:
a. A vertex in color class $i$ will only have neighbors in color classes $1, 2, \dots, i-1$.
b. This guarantees that the Greedy Coloring algorithm only needs $\chi(G)$ colors to properly color the graph.

6. Thus, Greedy Coloring uses exactly $\chi(G)$ colors.

7. By arranging vertices based on their color class from an optimal coloring, Greedy Coloring is guaranteed to use exactly $\chi(G)$ colors.