[그래프이론 (Graph Theory) 문제풀이] Find ordering of the vertices of G for which the greedy algorithm requires 3, and 4 colors, respectively.

그래프이론 (Graph Theory) 문제를 풀어보자. 이번에 풀어볼 문제는 “Find ordering of the vertices of G for which the greedy algorithm requires 3, and 4 colors, respectively.” 이다.

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

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

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

(풀이)
When an ordering is (g,e,d,f,h,b,a,c), coloring is (1,2,1,3,2,3,2,3).
When an ordering is (g,e,d,b,c,a,f,h), coloring is (1,2,1,2,3,4,3,4).

아래 그림 에는 e_4(H)=4 \leq 5이고 \chi(H)=5 인 그래프를 그려놨다.

참고글

[그래프이론 (Graph Theory) 문제풀이] Let ei(G) denote the number of vertices of G whose degree is strictly greater than i. Use the greedy algorithm to show that if ei(G) ≤ i + 1 for some i, then χ(G) ≤ i + 1. Find an example H that satisfies e4(H) ≤ 5 and compute χ(H).

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

[그래프이론 (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.)

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