Suppose that a graph has chromatic number $n$. If I choose $n$ vertices of the graph such that they do not form a $K_n$ (complete graph of $n$ vertices) can I colour them with $(n-1)$ colours, such that the rest of the graph can be coloured with $n$ colors?

  • $\begingroup$ you mean so that the rest of the graph can be colored with $n$ colors? $\endgroup$ – Jorge Fernández Hidalgo Mar 10 '15 at 14:07
  • $\begingroup$ Yes. I'll edit for clarity. $\endgroup$ – Allin Mar 10 '15 at 14:09

No. Let graph have edges $(0,1),(0,2),(0,3),(0,4),(1,4),(4,2),(2,3)$ It is not $2$-colourable since it contains a triangle but it is $3$-colourable $(0),(1,2),(3,4)$.

Drawing of the graph

Notice $0,1,3$ don't form a triangle but if they are $2$-coloured:

What happens if we attempt to color {0} and {1,3} the same color

Let $x$ be the colour of $0$ and $y$ the colour of $1,3$ then $z\not =x,y$ is the colour of $4$ but also $y$ must be the colour of $2$ so then $2,3$ have same colour contradiction.

In fact for any $n\ge 2$ you may take $G$ to be $K_{n+2}$ without edges in the path $v_1v_2v_3v_4$ where $v_i\in G$ for $i=1,..,4$ Now the property is not satisfied for $G-\{v_1,v_4\}$

  • $\begingroup$ Do you know a counterexample for n > 3 $\endgroup$ – Allin Mar 10 '15 at 18:02
  • $\begingroup$ Replied in the answer. $\endgroup$ – Leader47 Mar 11 '15 at 1:31

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.