×

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)

MSC:

05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: EuDML