on the color classes of a $k$ chromatic graph

Question

Let $G$ be a graph wich is $k$-chromatic. Suppose we have a coloring $(V_1, \ldots, V_l)$ such that each $V_i$ contains at least $2$ elements.

I want to prove that $G$ has a $k$-coloring with this property.

I was thinking of to do this by a contracdiction, but I don't know exactly in what way I have to think.

Is there someone who can take me on the right course?

Answer 1

Let's name your property, i.e. we will say that $k$-coloring $f : V \to [k]$ doesn't have unique colors if $$\forall c \in [k].\ \big|f^{-1}(c)\big| \geq 2.$$

Consider a $k$-chromatic graph $G = (V,E)$ and $L : V \to [l]$ for $l \in \mathbb{N}$ be any no-unique-colors $l$-coloring of $G$ (naturally $l \geq k$). We want to prove that there exists a $k$-coloring of $G$ with no unique colors.

I won't dwell on the details, instead I will sketch a proof that for any $k$-coloring we can decrease the number of colors which cover only a single vertex. (In a finite graph it means that applying that procedure repeatably we can obtain a $k$-coloring with no unique colors.)

Let $K_0$ be any $k$-coloring of $G$ and let's assume that there is a color $c_0$ which covers only one vertex $v_0$. However, in $L$ there was another vertex which was colored with the same color as $v_0$, let it be $u_0$. Set $K_1$ to be a coloring such that $K_1(u_0) = c_0$ and $K_1(v) = K_0(v)$ for any other $v \in V$. It has to be a valid coloring, but unfortunately it doesn't have to have unique colors.

Let $c_1 = K_0(u_0)$. There are some cases, e.g. if $K_1^{-1}(c_1)$ has two or more vertices we are done. However, the interesting one is when $K_1^{-1}\big(K(u_0)\big) = \{v_1\}$ for some vertex $v_1 \in V$. But then again, using $L$ we can find appropriate $u_1$, color it with $c_1$ in $K_2$, and then $v_2$, $u_2$, etc.

Note that:

• We won't repeat any $K$-color by following $L$-pairs (i.e. from $v_i$ to $u_i$).
• First time we find ourselves in a color of $L$ (i.e. going from $u_i$ to $v_{i+1}$) that we previously visited, we can color $v_{i+1}$ with the color we used previously, hence, produce $(k-1)$-coloring.
• By pigeonhole principle some color covers at least $3$ vertices (the graph has at least $2l \geq 2k$ vertices because of $L$).
• The graph is finite, so we can't loop forever.

This suggest that our sequence of colorings $K_0, K_1, K_2, \ldots$ terminates, and the last one decreases the number of vertices of unique color.

I hope this helps $\ddot\smile$