Find ordering of the vertices of G for which the greedy algorithm requires 3, and 4 colors,respectively.

문제출처

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

---

Solution

1. Let the index of colors be $\bigcirc < \triangle < \Box < \star$.

2. Let the ordering of vertices of $G$ be $g, d, e, c, f, a, b, h$.

• In this order, Greedy Coloring requires 3 colors. (See the left graph below.)

3. Let the ordering of vertices of $G$ be $g, e, d, f, b, h, c, a$.

• In this order, Greedy Coloring requires 4 colors. (See the right graph below.)

 

24년 기준으로는 해당 개념을 활용하는 문제가 시험에 출제된 바 있습니다. 후배님들은 참고바랍니다.