Mohar, Bojan; Škrekovski, Riste The Grötzsch theorem for the hypergraph of maximal cliques. (English) Zbl 0930.05040 Electron. J. Comb. 6, No. 1, Research paper R26, 13 p. (1999); printed version J. Comb. 6, 349-361 (1999). 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.] Reviewer: M.Frick (Pretoria) Cited in 4 ReviewsCited in 33 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05C65 Hypergraphs 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) Keywords:clique hypergraph; monochromatic; planar graph; list colorings PDFBibTeX XMLCite \textit{B. Mohar} and \textit{R. Škrekovski}, Electron. J. Comb. 6, No. 1, Research paper R26, 13 p. (1999; Zbl 0930.05040) Full Text: EuDML