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?
2
$\begingroup$
$\endgroup$
-
$\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
2
$\begingroup$
$\endgroup$
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\}$
