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

Horňák, Mirko; Jendrol’, Stanislav

Discuss. Math., Graph Theory 16, No. 2, 123-141 (1996).

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.

MSC:

05C75	Structural characterization of families of graphs
05C10	Planar graphs; geometric and topological aspects of graph theory

Keywords:

unavoidable set; plane graph; planar map; face types; cyclic chromatic number