[Graph Theory problem solving]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

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*}

[Graph Theory problem solving] Prove that if G is a color-critical graph, then the graph G′ generated from it by applying Mycielski’s construction is also color-critical. (If χ(H) < χ(G) for every proper subgraph H of G, then G is called color-critical.)

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

[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