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) \leq i + 1$ for some i, then $\chi(G) \leq i + 1$. Find an example H that satisfies $e_4(H) \leq 5$ and compute χ(H)

문제출처

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

---

Solution

1. Decide the order of all vertices.

2. First, place all the vertices with $deg_G(v) > i$. Next, place the remaining vertices.

3. By the given definition of $e_i(G)$, the number of vertices with $deg_G(v) > i$ is $e_i(G)$.

• By the given assumption, $e_i(G) \leq i+1$.
• Thus, $e_i(G)$ is at most $i+1$.

4. Apply the Greedy Coloring algorithm with this arrangement:

• First, vertices with $deg_G(v) > i$ will be colored. They need at most $i+1$ colors.
• The remaining vertices with $deg_G(v) \leq i$ are only adjacent to previously colored vertices, so no additional colors are required.

5. Therefore, by Greedy Coloring, $\chi(G) \leq i+1$.

6. Below is an example graph $H$ with $e_4(H) = 4 \leq 5$.

• This graph $H$ contains a subgraph $K_4$ (highlighted in orange). Thus, $\chi(H) \geq 4$.
• The graph is properly colored with 4 colors (1, 2, 3, 4), so it is 4-colorable.
• Therefore, $\chi(H) = 4$.