ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 16(2) (1996)
123-141 DOI: 10.7151/dmgt.1028
Mirko Horňák and Stanislav Jendrol
Department of Geometry and Algebra, P. J. Šafárik
Jesenná 5, 041 54 Košice, Slovakia
e-mail: firstname.lastname@example.org, jendrol@Košice.upjs.sk
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 𝒯 of face types is found
such that in any normal planar map there is a face with type from 𝒯. The set 𝒯
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.
Keywords: normal planar map, plane graph, type of a face, unavoidable set,
cyclic chromatic number.
1991 Mathematics Subject Classification: Primary 05C75, Secondary 05C10.