# Is there an efficient way for finding the chromatic number of a given graph?

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?

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.