I will solve a graph theory problem:

For n ≥ 1, let Gn = Pn□K2 ; this is the graph with 2n vertices and 3n − 2 edges shown below. Determine χ(Gn; k). (You should simplify your answer by factoring the polynomial

## Graph Theory Problem Solving:

$G_n$ is a bipartite graph. Therefore, it should be $k\geq 2$.

Let $P_n$ be denoted as $v_1-v_2-…-v_n$. $\chi\left(P_n[\{v_1\}] \square K_2;k\right) = k(k-1)$. Consider $\chi\left(P_n[\{v_1,v_2\}] \square K_2;k\right)$ under the condition where vertices of $P_n[\{v_1\}]\square K_2$ are colored. There are two cases: case1) $(v_2,2)$ is colored by the same color used for $(v_1,1)$, case2) $(v_2,2)$ is colored by the color not used for $(v_1,1)$. The number of ways coloring for case 1) is $(k-1)$ and the number of ways coloring for case 2) is $(k-2)^2$. Therefore, $\begin{align*}\chi\left(P_n[\{v_1,v_2\}] \square K_2;k\right) &= \chi\left(P_n[\{v_1\}] \square K_2;k\right) \times \left( (k-1)+ (k-2)^2 \right)\\ & = \chi\left(P_n[\{v_1\}] \square K_2;k\right) \times (k^2-3k+3) \end{align*}$

Similarily, $\chi(P_n[ \{v_1,v_2,v_3,..,v_{i}, v_{i+1}\}]\square K_2 ;k )= \chi(P_n[ \{v_1,v_2,v_3,..,v_{i}\}]\square K_2 ;k )\times (k^2-3k+3)$.

Therefore

\begin{align*}

\chi(P_n \square K_2;k) &=\chi\left(P_n[\{v_1\}]\square K_2 ;k\right) \left( (k^2-3k+3) \right)^{n-1} \\ &= k (k-1)(k^2-3k+3)^{n-1}

\end{align*}

Related Posts:

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

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