Kobler, Daniel; Kündgen, André Gaps in the chromatic spectrum of face-constrained plane graphs. (English) Zbl 0984.05036 Electron. J. Comb. 8, No. 1, Research paper N3, 4 p. (2001). Authors’ abstract: Let \(G\) be a plane graph whose vertices are to be colored subject to constraints on some of the faces. There are 3 types of constraints: a \(C\) indicates that the face must contain two vertices of a \(C\)ommon color, a \(D\) that it must contain two vertices of a \(D\)ifferent color and a \(B\) that \(B\)oth conditions must hold simultaneously. A coloring of the vertices of \(G\) satisfying the facial constraints is a strict \(k\)-coloring if it uses exactly \(k\) colors. The chromatic spectrum of \(G\) is the set of all \(k\) for which \(G\) has a strict \(k\)-coloring. We show that a set of integers \(S\) is the spectrum of some plane graph with face-constraints if and only if \(S\) is an interval \(\{s,s+1,\dots, t\}\) with \(1\leq s\leq 4\), or \(S= \{2,4,5,\dots, t\}\), i.e. there is a gap at \(3\). Reviewer: Timothy R.Walsh (Montreal) Cited in 12 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05C10 Planar graphs; geometric and topological aspects of graph theory Keywords:colorings of hypergraphs; mixed hypergraphs; planar graphs and hypergraphs; colorability; chromatic spectrum PDFBibTeX XMLCite \textit{D. Kobler} and \textit{A. Kündgen}, Electron. J. Comb. 8, No. 1, Research paper N3, 4 p. (2001; Zbl 0984.05036) Full Text: EuDML EMIS