0
$\begingroup$

This is supposidly True in the key

but a pentagon is non-4-colorable and removing a vertex (either deletion or contraction) leaves a 2 colorable graph.

anyone know anything about this or is it just a typo?

$\endgroup$
  • $\begingroup$ What key?${}{}{}{}{}{}{}{}{}{}$ $\endgroup$ – user122283 Apr 3 '14 at 1:49
  • $\begingroup$ A pentagon is $4$-colorable. Non $k$-colorable means you need more than $k$ colors to properly color the graph. $\endgroup$ – hbm Apr 3 '14 at 2:00
0
$\begingroup$

A pentagon is $C_{5}$. That is three-colorable. I begin at $v_{0}$ and color that red. I then color $v_{0}$'s neighbors, $v_{1}$ and $v_{2}$, blue. I then color $v_{1}$'s uncolored neighbor, $v_{3}$, red. I now have $v_{4}$, which is adjacent to $v_{2}$ (blue) and $v_{3}$ (red). So $v_{4}$ needs to be colored green. Thus, removing $v_{4}$ leaves a two-colorable graph- $P_{4}$, a path on four vertices.

$\endgroup$

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.