# 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).