Confusion about a proof on Mycielski construction and chromatic number

Question

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')$?

Answer 1

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.

Answer 2

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.

Answer 3

I think the proof in that book might be flawed.

If $x$ and $y$ are adjacent vertices of $F$ such that their shadow vertices have the same color (that is $c(x')=c(y')$), then replacing the colors as in the proof will not give a proper coloring.

There is no (obvious to me) reason why this cannot happen.

Both answers ignore this issue by assuming that if a vertex changes colour, then none of its neighbours does.

To fix this, only recolor vertices of $F$ that have the same colour as $z$. (And change their color to the one of their shadow, as in the book.) One can check this is a proper colouring of $F$.