# A problem in graph coloring, inspired by the 4CT

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

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

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'$$.