# Colouring $n$ vertices with $(n-1)$ colours in a graph with chromatic number $n$

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?

• you mean so that the rest of the graph can be colored with $n$ colors? – Jorge Fernández Hidalgo Mar 10 '15 at 14:07
• Yes. I'll edit for clarity. – 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)$.

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

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\}$

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