Unavoidable set of face types for planar maps. (English) Zbl 0877.05048

Summary: The type of a face \(f\) of a planar map is a sequence of degrees of vertices of \(f\) as they are encountered when traversing the boundary of \(f\). A set \(\mathcal T\) of face types is found such that in any normal planar map there is a face with type from \(\mathcal T\). The set \(\mathcal T\) has four infinite series of types as, in a certain sense, the minimum possible number. An analogous result is applied to obtain new upper bounds for the cyclic chromatic number of 3-connected planar maps.


05C75 Structural characterization of families of graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI Link