I will solve a graph theory problem:

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:

Let $V(G) = \{v_1,v_2,…,v_n\}$ and $V(G^\prime) = V(G) \cup \{ u_1,u_2,…,u_n \} \cup \{ w \}$ and $E(G^\prime) = E(G) \cup \{ \cup_{i=1}^n \{ u_i v \mid v \in N_G (v_i) \} \}$.

It is sufficent to prove that $G^\prime$ is a color-critical graph, when $G^\prime$ is a connected graph. Therefore, it is enough to prove that $G^\prime-e$ is a color-critical graph for $e \in E(G^\prime)$.

Let $V(G) = \{v_1,v_2,…,v_n\}$ and $V(G^\prime) = V(G) \cup \{ u_1,u_2,…,u_n \} \cup \{ w \}$ and $E(G^\prime) = E(G) \cup \{ \cup_{i=1}^n \{ u_i v \mid v \in N_G (v_i) \} \}$.It is sufficient to prove that $G^\prime$ is a color-critical graph when $G^\prime$ is a connected graph. Therefore, it is enough to prove that $G^\prime-e$ is a color-critical graph for $e \in E(G^\prime)$.\\

Case1) $e=v_iv_j$ for $i \neq j$. There exists a proper $(k-1)$-coloring $f$ for $G-e$. Let $g: V(G^\prime) \to \{1,2,…,k\}$ such that $g(w)=1$, $g(v_l) = f(v_l)$ for all $l=1,2,..n$ and $g(u_l)=k$ for all $l=1,2,3,…n$.\\

Case2) $e=v_iu_j$ for $i \neq j$. Then $v_i \in N_G(v_j)$. Let $H=G-v_iv_j$. Let $H^\prime$ be a graph from $H$ by Mycielski’s construction. Then $G^\prime-e = H^\prime + v_iv_j+v_ju_i$. Since $H$ is a proper subgraph of $G$, there exists a proper $(k-1)$-coloring $f$ for $H$. Let $g: V(G^\prime-e) \to \{1,2,…,k\}$ such that $g(v_j)=k$, $g(w)=k$ , $g(u_j) = f(v_j)$ , $g(u_l) = g(v_l) = f(v_l)$ for all $l \in \{ 1,2,3,…,n\}-j$.\\

Case3) $e=u_i w$ for some $i$. Let $H=G-v_i$. There exists a proper $(k-1)$-coloring $f:V(H) \to \{1,2,…,k-1\}$. Let $g : V(G^\prime) \to \{1,2,3,…,k\}$ such that $g(v_i)=g(u_i)=g(w)=k$ and $g(v) =f(v)$ for remaning vertices.

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