What can we say about the colourings of some subset of vertices of a graph

35 Views Asked by At

I will clarify the question by defining some straightforward concepts.

Let G = (V, E) be a simple graph with chromatic number $k$. We call a subset $V'\subset V$ fully chromatic if every proper k-colouring of G uses also $k$ distinct colors on $V'$. We say such a fully chromatic set is minimal, if every subset of $V'$ is not fully chromatic.

Now I conjecture that for every G=(V, E) and every minimally chromatic set $V'\subset V$, there exists some graph $G^* = (V^*, E^*) $ that has the same proper k-colourings on $V^*$ as all proper k-colourings of $G$ restricted to $V'$.

Furtermore, I conjecture that $G$ has $G^*$ as a minor