[그래프이론 (Graph Theory) 문제풀이] For every graph G, show that there is an ordering of the vertices of G such that the number of required colors from Greedy Algorithm is exactly χ(G). (You should describe how to give such an order.)

그래프이론 (Graph Theory) 문제를 풀어보자. 이번에 풀어볼 문제는 “For every graph G, show that there is an ordering of the vertices of G such that the number of required colors from Greedy Algorithm is exactly χ(G). (You should describe how to give such an order.)” 이다.




그래프이론 (Graph Theory) 문제풀이

이번에 풀고자 하는 그래프이론 (Graph Theory) 문제는 아래와 같다.

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

(풀이)
k:=\chi(G) 라고 하자. 그러면 k-proper coloring f:V(G) \to \{1,2,3,...,k\} 가 존재한다. I_i= \{ v \in V(G) \mid f(v) = i \} 라고 하자.  I_i = \{ v_{i,1}, v_{i,2},...,v_{i,n(i)} \} 라고 하자. v_{1,1},v_{1,2},...,v_{1,n(1)},v_{2,1},v_{2,2},..., v_{2,n(2)},v_{3,1},v_{3,2},...,v_{3,n(3)},....,v_{k,1},v_{k,2},...,v_{k,n(k)} 순으로 vertices들을 나열하자. 이렇게 되면 Greedy algorithm 을 사용할 경우 k 개를 이용해서 색칠할 수 있다.

 

참고글

[그래프이론 (Graph Theory) 문제풀이] Choose two graphs and determine the chromatic numbers of them. Give your explanation for each case.

 

문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 7 문제

Leave a Comment