Let $G$ be any simple graph (i.e has no loops nor multiple edges) and let $1,2,...,\chi(G)$ be any good coloring to the vertices of $G$(i.e a minimal coloring for its vertices in which each 2 adjacent vertices have different colors).

let $v$ be a vertex in $G$ of color $1$ such that $v$ has no neighbors of color $2$.

show that $\chi(G-\{v\})=\chi(G)$.

Thank you for helping.

  • $\begingroup$ What's the source of this problem, please? $\endgroup$ – Gerry Myerson May 11 '14 at 11:57
  • $\begingroup$ my problem is that if i color the vertices of a graph (in which each 2 adjacent vertices have different colors and with minimal number of colors ) and i want to remove a vertex such that there is some color not obtained in its neighbors , Did the chromatic number still the same? or it will decrease one ? $\endgroup$ – mohamad nasser May 11 '14 at 13:35
  • $\begingroup$ I tried to find an example and i see that it will be the same but i couldnt prove it theoretically! Any help please $\endgroup$ – mohamad nasser May 11 '14 at 21:47
  • $\begingroup$ What I meant was, where did you find this problem? $\endgroup$ – Gerry Myerson May 11 '14 at 23:06
  • $\begingroup$ In my work on the stage i have something like that related to forests ... but this is a little bit general. $\endgroup$ – mohamad nasser May 12 '14 at 2:09

The problem is false, Indeed, Consider a cycle of 5 vertices colored by the colors 1,2,1,2,3 then the third vertex colored by color 1 and not adjacent to the color 3, but removing it obtain a path which can be colored by 2 colors.


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.