I have a conjecture regarding vertex coloring Let $G = (V, E)$ be a graph with chromatic number $n+1$, and let there be some vertex $v* \in V$, so that deleting this vertex results in a graph $G/{v*}$ that has chromatic number n.
Now, assign to $G/{v*}$ any proper n-coloring, then color  $v*$ in the $(n+1)-th$ color.
Rainbow Conjecture:
Choose at least 2 (and at most n) distinct colors from the first n colors, and order these in any way. I conjecture that there exists a cycle in $G$ that contains $v*$, and so that the colors we come across when we traverse this cycle  starting from $v*$, are precisely (one or multiple) repetitions of the chosen pattern.
So cycles are for example colored like: $v*$ - blue - green - red - ($v*$) , or $v*$- blue- red - blue - red - ($v*$). And these cycles exist for all proper n-colorings of $G/{v*}$ and any combination and order of the n colors.
The reason why I think this might be true is because if there would be an ordering that doesn't have a matching path that starts at $v*$, for example: if we can't go from $v*$ to a red vertex and then a green vertex, then all red neighbors of $v*$ don't have green neighbors, so we could change them all to green, but then we could change $v*$ to red, which would result in a $n$-coloring of $G$. But this doesn't really explain why the path must also come back to $v*$. My conjecture seems quite optimistic, however, I haven't been able to find a counter example.
What do you guys think? Thanks for your time, and I'd love to see if someone can find a counterexample (or a proof even better). I guess counterexamples would have generally high girth or low clique.
 A: Your conjecture is true, and your attempt was aiming in the right direction. Let $c_1, ..., c_k$ be a sequence of colors. Suppose by contradiction that you can find such a cycle. Let $S$ be the set of vertices that can be reached by a path starting from $v*$ and alternating colors in the correct order. By definition, if a vertex in $S$ is colored by $c_i$, its neighbors outside of $S$ can't be colored with $c_{i+1}$ (modulo $k$). Then it is easy to see that we can switch for each vertex in $S$ color $c_i$ by color $c_{i+1}$ (modulo $k$). Because no vertices colored by $c_k$ in $S$ was adjacent to $v*$, with the color switch, no vertices colored with $c_1$ is adjacent to $v*$, so $v*$ can then be colored by $c_1$, thus the contradiction.
When we have two colors, $S$ is equivalent to a Kempe chain. In the general setting, it provides a generalization of Kempe chains. I never encountered this concept of generalized Kempe chains, I don't know if it exist in literature, but it seems to be a useful concept.
Edit: Generalized Kempe chains are mentionned in the "Handbook of Combinatorics Volume 1", chapter 4.5.3
