Prove that a graph G is m-colorable if and only if α(G□Km) ≥ n(G).

문제출처

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

---

Solution

1. ($\Rightarrow$) If $G$ is $m$-colorable:

• Assume there exists a proper $m$-coloring $f : V(G) \to {1, 2, \ldots, m}$. For each color $i$, let $I_i = {v \in V(G) \mid f(v) = i}$. Each $I_i$ is an independent set in $G$.

• Consider the Cartesian product $G \square K_m$. The vertex set of $G \square K_m$ is:
  $$V(G \square K_m) = {(x, i) \mid x \in V(G), i \in {1, \ldots, m}}.$$

• Define $J_i = {(x, i) \mid x \in I_i}$. Since $I_i$ is independent in $G$, for distinct vertices $x_1, x_2 \in I_i$, $(x_1, i)$ and $(x_2, i)$ are not adjacent in $G \square K_m$. Moreover, if $(x_1, i)$ and $(x_2, j)$ with $i \neq j$ were adjacent, it would contradict the definition of the Cartesian product and independence sets.

• Thus, all $(x, i) \in J = \bigcup_{i=1}^m J_i$ form a large independent set in $G \square K_m$.

• Since each $J_i$ corresponds exactly to the independent set $I_i$ in $G$, we have $|J_i| = |I_i|$. Therefore,
  $$|J| = \sum_{i=1}^m |J_i| = \sum_{i=1}^m |I_i| = |V(G)| = n(G).$$

• This shows that $\alpha(G \square K_m) \geq n(G)$.

2. ($\Leftarrow$) If $\alpha(G \square K_m) \geq n(G)$:

• Suppose there is an independent set $J \subseteq V(G \square K_m)$ with $|J| \geq n(G)$.

• Partition $J$ according to the second coordinate (the $K_m$-part) as:
  $$J = \bigcup_{i=1}^m J_i, \quad \text{where } J_i = {(x, i) \in J}.$$

• Define $L_i = {x \in V(G) \mid (x, i) \in J}$. Since $(x, i)$ and $(y, i)$ are in the same independent set $J_i$, no two distinct $x, y \in L_i$ are adjacent in $G$. Thus, each $L_i$ is an independent set in $G$.

• Because ${L_i}$ partitions $V(G)$ and $|L_i| = n(G)$, we have found an $m$-coloring of $G$ where each color class is one of the $L_i$'s.

• Therefore, $G$ is $m$-colorable.