×

Gaps in the chromatic spectrum of face-constrained plane graphs. (English) Zbl 0984.05036

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\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: EuDML EMIS