A problem in graph coloring, inspired by the 4CT

Question

Let $G = (V, E) $ be a simple k-chromatic graph. A coloring of $G$ can be assumed to imply a proper k-coloring on the vertices.

We call a set of vertices $V'\subset V$ fully chromatic if for any coloring of $G$, all colors are present in $V'$. If $V'$ is minimal, in the sense that all subsets are not fully chromatic, then we call $V'$ critically fully chromatic.

Now I believe that a k-chromatic graph can't have a critically fully chromatic subset of size $k+1$. In the case k=4, this would simplify the proof of the 4CT by a lot.

Can some come up with such a critical chromatic set of vertices of size $k+1$?

Answer 1

For an example of this when $k=3$, take the $6$-vertex graph whose vertices are arranged in a $2 \times 3$ grid, and vertices are adjacent if they are in the same row or column. Here are some $3$-colorings of this graph (where A, B, and C are the colors):

A B C    A B C
B C A    C A B

Up to permuting the colors, these are the only two possible colorings.

In particular, it is impossible to color a $2 \times 2$ subgrid with just $2$ colors, so the vertices of a $2\times 2$ subgrid are a fully chromatic set. However, for every $3$-vertex subset of a $2\times 2$ subgrid, one of the colorings above shows that it can be colored with just $2$ colors. So there is a $(k+1)$-vertex minimal fully-chromatic set.

A straightforward way to get examples for all $k>3$ from here is to add $k-3$ new vertices adjacent to every old vertex and each other, and include them in $V'$.