4
$\begingroup$

On an exam, I was given the Peterson graph and asked to find the chromatic number and a vertex coloring for it.

I spent quite some time playing around with different colorings and incorrectly concluded the chromatic number was 4 because I could not at the time find one using 3 colors.

The answer turns out to be 3 and once I saw a 3-coloring solution I felt silly for not seeing it while taking the exam.

My question is, given a graph and asked to find the chromatic number and a corresponding vertex coloring, is there a better way to find it other than the guess and check method?

$\endgroup$
4
$\begingroup$

1) What I heard is that, it is conjectured that the problem of determining a graph is 3-colorable or not does not have a polynomial time algorithm.

2) Brooks' theorem states that any graph that is neither complete nor an odd cycle satisfies: $$\chi(G)\leq \triangle(G)$$ Thus, Brooks' theorem can be used to deduce that the Petersen graph is 3-colorable.

$\endgroup$
  • $\begingroup$ This is excellent and exactly the sort of answer I was looking for. I was hoping that there would be a theorem to help conclude what the chromatic number of a given graph would be. $\endgroup$ – Joseph DiNatale Dec 2 '13 at 18:07
  • 2
    $\begingroup$ @user2521987 Note that Brook's theorem only allows you to conclude that the Petersen graph is 3-colorable and not that its chromatic number is 3 $\endgroup$ – Amr Dec 2 '13 at 21:02

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.