[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.)

by






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).

[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

Leave a Comment