Theorem 10.10 of the textbook "A First Course in Graph Theory (2012)" by Gary Chartrand and Ping Zhang is as follows:

For every integer $k \ge 3$, there exists a triangle-free graph with chromatic number $k$.

This is proved by induction on $k$ and in the inductive step it actually shows that

From a $(k-1)$-chromatic triangle-free graph $F$, Mycielski's construction produces a $k$-chromatic triangle-free graph $G$.

The Mycielski's construction (wiki) of $F$ is obtained from $F$ by first adding, for each vertex of $F$, a new vertex $v'$, called the shadow vertex of $v$, and joining $v'$ to the neighbors of $v$ in $F$ and then adding a new vertex $z$ and joining $z$ to all the shadow vertices.

For the part the correctness of $\chi(G) = k$, it proceeds as follows:

Assume, to the contrary, that $\chi(G) = k-1$. Let there be a $(k-1)$-coloring $c$ of $G$, say with colors $1, 2, \ldots, k-1$. We may assume that $c(z) = k-1$. Since $z$ is adjacent to every shadow vertex in $G$, it follows that the shadow vertices are colored with the colors $1, 2, \ldots, k-2$. For every shadow vertex $x'$ of $G$, the color $c(x')$ is different from the colors assigned to the neighbors of $x$. Therefore, if for each vetex $y$ of $G$ belonging to $F$, the color $c(y)$ is replaced by $c(y')$, we have a $(k-2)$-coloring of $F$. This is impossible, however, since $\chi(F) = k - 1$.

My Problem: The argument in bold does not seem clear to me. How to make sure that the resulting coloring is a proper coloring? In other words, how to show that for each pair of adjacent vertices $u,v$ in $F$, $c(u') \neq c(v')$?


The proof aims to show $\chi(G) = k$ and has two parts.

First, they show that $\chi(G) \leq k$.

The second part of the proof is showing that $\chi(G) \geq k$. This is the part that concerns the bolded argument in your post.

To prove this, the authors suppose BWOC, that $\chi(G) \ngeq k$. Then there is a $k-1$ coloring of $G$. The vertex $z$ can be colored using the color $k-1$ and the shadow vertices can be colored using $k-2$ colors.

At this point the bolded statement comes in: therefore, if for each vetex 𝑦 of 𝐺 belonging to 𝐹, the color 𝑐(𝑦) is replaced by 𝑐(𝑦′), we have a (𝑘−2)-coloring of 𝐹.

The authors are saying to give each vertex $y$ in $F$ the same color as their shadow vertex $y'$. Why do we know this is a proper coloring? Since every vertex that is adjacent to $y$ in $F$ is also adjacent to $y'$ in $G$, then $y'$ must have a different color to every neighbor of $y$.

This fact essentially says that if we have a proper $k-1$ coloring of $G$, we don't have to use the color of $z$ (i.e. $c(z)$) for any of the vertices of $F$. So we would have a proper $k-2$ coloring of $F$ which is the desired contradiction.


Based on the assumption that $c(z)=k-1$, since $z$ is only adjacent to the set of shadow vertices of $F$, we know that the set of shadow vertices is $k-2$ colorable.

Now to address your question; When applying a proper coloring to a Mycielski's Constructed graph, it is possible to assign $c(y)=c(y')$. That is, a shadow vertex $y'$ can have the same color as $y$. This is because each shadow is not adjacent it's origin in the constructed graph.

Hence, because the set of shadow vertices is $k-2$ colorable, without any colors already imposed on $F$, we color $F$ so that $c(y)=c(y')$ for each $y\in V(F)$. Thus, providing a $k-2$ coloring on $F$ which contradicts how $F$ was defined.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.