The Grötzsch theorem for the hypergraph of maximal cliques (Q1292236)

The clique hypergraph \({\mathcal H}(G)\) of a graph \(G\) is the hypergraph with the same vertex set as \(G\), whose (hyper)edges are the maximal cliques of \(G\). A \(k\)-coloring of \({\mathcal H}(G)\) is a coloring of the vertices of \({\mathcal H}(G)\) such that no hyperedge is monochromatic. The main result of this paper is that the clique hypergraph of any planar graph is 3-colorable, thus extending Grötzsch's result that every triangle-free planar graph is 3-colorable. The authors also extend this result to list colorings, by proving that \({\mathcal H}(G)\) is 4-choosable for every planar or projective planar graph \(G\). [Due to an error in the pagination of the printed version there is some overlapping of pages with the preceding paper.]