Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How is graph coloring related to the maximum clique structure inside a graph? Also, is graph coloring problem only studied for planar graphs?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The presence of a clique $K_n$ in a graph implies that the graph is not $(n-1)$-colorable. However, the converse is not true, e.g., the Grötzsch graph has no triangle ($K_3$), but is not $3$-colorable (this generalizes to the Mycielskian, which gives triangle-free graphs with arbitrarily high chromatic number).

The graph coloring problem is not only studied for planar graphs, although, historically, motivation for studying graph coloring problems came from attempts to find a proof for the Four Color Theorem for planar graphs.

George David Birkhoff introduced the chromatic polynomial in 1912, defining it only for planar graphs, in an attempt to prove the four color theorem. -- Wikipedia.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.