How is graph coloring related to the maximum clique structure inside a graph? Also, is graph coloring problem only studied for planar graphs?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.