Premium
Cyclic degree and cyclic coloring of 3‐polytopes
Author(s) -
Borodin Oleg V.
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199611)23:3<225::aid-jgt2>3.0.co;2-u
Subject(s) - combinatorics , polytope , mathematics , bounding overwatch , degree (music) , brooks' theorem , lebesgue integration , vertex (graph theory) , upper and lower bounds , complete coloring , list coloring , graph , discrete mathematics , graph power , line graph , computer science , physics , artificial intelligence , acoustics , mathematical analysis
A vertex coloring of a plane graph is called cyclic if the vertices in each face bounding cycle are colored differently. The main result is an improvement of the upper bound for the cyclic chromatic number of 3‐polytopes due to Plummer and Toft, 1987 ( J. Graph Theory 11 (1987) 505–517). The proof is based on a structural property of 3‐polytopes, in a sense stronger than that implied by Lebesgue's theorem of 1940. Namely, precise upper bound is obtained for the minimum cyclic degree of 3‐polytopes with the maximum face size at least 24. © 1996 John Wiley & Sons, Inc.