[Graph Theory problem solving] Prove that a graph G is m-colorable if and only if α(G□Km) ≥ n(G).

I will solve a graph theory problem:

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

Graph Theory Problem Solving:

($\Rightarrow$) Since $G$ is m-colorable, there exists a proper m-coloring $f:V(G) \to \{1,2,…,m\}$. For each $i=1,2,3,…,m$, let $I_i = \{ v \in V(G) \mid f(v) =i \}$. $I_i$ is an independent set for each $i$. Let $J_i = \{ (x,i) \mid x \in I_i \}$ for each $i=1,2,3,…m$ and $J = \cup_{i=1}^m J_i$. Then $|J| = \sum_{i=1}^m |J_i| = \sum_{i=1}^m |I_i| = n(G)$. Let $(x_1, i_1), (x_2, i_2) \in J$. If $i_1=i_2$, then $x_1$ and $x_2$ are not adjacent, since $x_1,x_2 \in I_{i_1}$. If $i_1 \neq i_2$, then $x_1 \neq x_2$ and $x_1$ cannot be adjacent to $x_2$. Since $|J|=n(G)$, $\alpha(G\square K_m) \geq n(G)$\\
($\Leftarrow$) Since $\alpha(G \square K_m) \geq n(G)$, there exists an independent set $J \subset V(G \square K_m)$ such that $|J| \geq n(G)$. For each $i=1,2,3,…,m$, let $J_i = \{ (x,y) \in J \mid y=i \}$ and $L_i = \{ x \in V(G) \mid (x,i) \in J_i \}$. By the constructions above, $|L_i|= |J_i|$ for each $i$ and $\{J_i\}_{1\leq i \leq m} $ are a collection of disjoint sets. By the definition of $J_i$, $J = \cup_{1 \leq i \leq m} J_i$.
If $x \in L_{i_1} \cap L_{i_2}$ for distinct indices, $(x,i_1)$ and $(x,i_2)$ belong to an independent set $J$. It is an contradiction to the fact $(x,i_1)$ and $(x,i_2)$ are adjacent. Therefore, $L_i$s are disjoint sets. From an inequality $|J| = \sum_{i=1}^m |J_i| = \sum_{i=1}^m |L_i | \geq | n(G)|$ and the fact that $L_i$s are disjoint, $V(G) = \cup_{i=1}^m L_i$. If $x$ and $y$ are two distinct vertices in $L_i$, then $(x,i)$ and $(y,i)$ are not adjacent, it means that $x$ and $y$ are not adjacent in $G$. Therefore, $L_i$ is an independent set for each $i$. Since there are $m$ independent sets $L_1,L_2,…,L_m$, $G$ is $m$-colorable.

Related Posts:

[Graph Theory problem solving] Deduce that $e(T_{n,k}) = \left \lfloor \left(\frac{k-1}{2k} \right) n^2\right \rfloor$ for all $k < 8$

[Graph Theory problem solving] Show that $(\frac{k-1}{2k})n^2 – \frac{1}{8 k} \leq e (T_{n,k}) \leq (\frac{k-1}{2k}) n^2$.

[그래프이론 (Graph Theory) 문제풀이] The Turan graph T_{n,r} is the compelete r-partite graph with b partite sets of size a+1 and r − b partite sets of size a, where a = \lfloor n/r\rfloor and b = n − ra. (a) Prove that e(T_{n,r}) =\left( 1- \frac{1}{r} \right)\frac{n^2}{2} - \frac{b(r-b)}{2r} . (b) Since e(G) must be an integer, part (a) imples e(T_{n,r}) ≤ \lfloor (1-\frac{1}{r}) \frac{n^2}{2} \rfloor Determine when strict inequality occurs

Source: Homework problem from Professor Choi‘s Graph Theory class, Gwangju Institute of Science and Technology, Fall Semester 2023