If $G$ is a simple graph which has chromatic number $\chi(G)$ is it true to claim that there is a $(\chi(G)-1)$-regular induced subgraph?

I've been trying to prove it. It seems as though it should be true. There must be at least one vertex $v$ of colour $1$, in a $\chi(G)$ colouring of $G$, which cannot change colour. This would contradict that $G$ has chromatic number $\chi(G)$. So $v$ has at least a neighbour of every other colour $2,...,\chi(G)$. For each colour, at least one neighbour of $v$ which is that colour, can't change colour. If it could $v$ could change colour. Therefore, this neighbour must also have at least one neighbour of every other colour...and so. until eventually this chain of vertices, which are unable to change colour, will form an $(\chi(G)-1)$-regular induced subgraph.

Does any one know if this claim is true? Is there an obvious counter example? Could any one prove it?


1 Answer 1


Take a look of this graph $G$ in Wikipedia. $\chi(G)=4$, but there is no $3$-regular induced graph, I have checked it by tedious exhausting approach: First, show that the green vertex in left-upper region cannot be in such induced graph, then we can eliminate many possibilities consequently.

By the way, your proposition holds for $\chi(G)\leq 3$ trivially.

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.