The Grötzsch Theorem for the Hypergraph of Maximal Cliques

Abstract

In this paper, we extend the Grötzsch Theorem by proving that the clique hypergraph ${\cal H}(G)$ of every planar graph is 3-colorable. We also extend this result to list colorings by proving that ${\cal H}(G)$ is 4-choosable for every planar or projective planar graph $G$. Finally, 4-choosability of ${\cal H}(G)$ is established for the class of locally planar graphs on arbitrary surfaces.