# Maximum Clique Structure and Graph Coloring

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

-

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.

-