[그래프이론 (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) 문제를 풀어보자. 이번에 풀어볼 문제는 “Let e_i(G) denote the number of vertices of G whose degree is strictly greater than i. Use the greedy algorithm to show that if e_i(G) ≤ i + 1 for some i, then χ(G) ≤ i + 1. Find an example H that satisfies e_4(H) ≤ 5 and compute χ(H).” 이다.

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

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

Let e_i(G) denote the number of vertices of G whose degree is strictly greater than i. Use the greedy algorithm to show that if e_i(G) ≤ i + 1 for some i, then χ(G) ≤ i + 1. Find an example H that satisfies e_4(H) ≤ 5 and compute χ(H).

(풀이)
Greddy algorithm 을 사용하기 위해 vertices의 순서를 정해야 한다.
deg_G(v) > i 인 vertices 모두를 먼저 놓는다.
그 이후 deg_G(v) \leq i 인 vertices들을 놓는다.
deg_G(v) > i 인 vertices 의 총갯수는 e_i(G)이다.
e_i(G)는 많아야 i+1이다.
vertcies에 메겨진 순서에 따라 Greedy Algorithm 시행 시 degree 가 deg_G(v) > i 인 vertices들을 색칠하기 위해 많아야 i+1개의 색이 필요하다.
나머지 vertex 의 degree 는 많아야 i 이다.
이 나머지 vertex 까지 색칠하는데 최대 i+1 개의 색이 필요하다.
따라서 \chi(G) \leq i +1 .

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

참고글

[그래프이론 (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 문제