A cyclic coloring of a planar embedding is a vertex coloring such that vertices incident with
the same face have distinct colors. The minimum number of colors in a cyclic coloring
of a graph is called the cyclic chromatic number of the graph, variously denoted
(Plummer and Toft 1987, Zlámalová 2010) or (Borodin et al. 2007).
Sanders and Zhao (2001) proved that
where
is the maximum face degree of a graph. The notation is sometimes used in place of (e.g., Plummer and Toft 1987), as is (e.g., Tilley et al. 2024). The cyclic coloring conjecture
states is an important extension of the four-color
theorem which states that
(Borodin 1984, Plummer and Toft 1987, Tilley et al. 2024). The conjecture becomes a theorem in the case of a facially
complete planar embedding (Chen et al. 1998, Tilley et al. 2024).
It is conjectured that for polyhedral
graphs (Plummer and Toft 1987, Horňák and Zlámalová
2010). The numbers of polyhedral graphs on , 2, ... in for which are given by 0, 0, 0, 0, 0, 1, 1, 3, 18, 129, ...
(E. Weisstein, Sep.3, 2024). These include stacked 3-prism graphs. Two additional
infinite families of such graphs were noted by Plummer and Toft (1987), the first
of which are known in this work as Plummer-Toft
graphs.
Borodin, O. V. "Solution of the Ringel Problem on Vertex-Face Coloring of Planar Graphs and Coloring of 1-Planar Graphs." Metody
Diskret. Analiz.41, 12-26, 1984.Borodin, O. V.; Sanders,
D.; and Zhao, Y. "On Cyclic Colorings and Their Generalizations." Disc.
Math.203, 23-40, 1999.Borodin, O. V.; Broersma, H. J.;
Glebov, A.; and van den Heuvel, J. "A New Upper Bound on the Cyclic Chromatic
Number." J. Graph Th.54, 58-72, 2007.Chen, Z.; Grigni,
M.; and Papadimitiou, C. "Planar Map Graphs." In Proc. 30th Symposium
on Theory Computing, pp. 514-523, 1998.Enomoto, H.; Horňák,
M.; and Jendrol', S. "Cyclic Chromatic Number of 3-Connected Plane Graphs."
SIAM J. Disc. Math.14, 121-137, 2001.Horňák,
M. and Zlámalová, J. "Another Step Towards Proving a Conjecture
by Plummer and Toft." Disc. Math.310, 442-452, 2010.Jensen,
T. R. and Toft, B. Graph Coloring Problems. New York: Wiley, 1995.Ore,
O. and Plummer, M. D. "Cyclic Coloration of Plane Graphs." In Recent
Progress in Combinatorics, Proceedings of the Third Waterloo Conference on Combinatorics.
San Diego, CA: Academic Press, pp. 287-293, 1969.Plummer, M. D.
and Toft, B. "Cyclic Coloration of 3-Polytopes." J. Graph Th.11,
507-515, 1987.Sanders, D. P. "A New Bound on the Cyclic Chromatic
Number." J. Combin. Th., Ser. B83, 102-111, 2001.Sanders,
D. P. and Zhao, Y. "A New Bound on the Cyclic Chromatic Number." J.
Combin. Th., Ser. B83, 102-111, 2001.Tilley, J.; Wagon,
S.; and Weisstein, E. "A Catalog of Facially Complete Graphs." 17 Sep 2024.
https://arxiv.org/abs/2409.11249.Zlámalová,
J. "A Note on Cyclic Chromatic Number." Discuss. Math. Graph Th.30,
115-122, 2010.
(Plummer and Toft 1987, Zlámalová 2010) or 
(Borodin et al. 2007).
is the maximum face degree of a graph. The notation 
is sometimes used in place of 
(e.g., Plummer and Toft 1987), as is 
(e.g., Tilley et al. 2024). The cyclic coloring conjecture
states is an important extension of the four-color
theorem which states that
for polyhedral
graphs (Plummer and Toft 1987, Horňák and Zlámalová
2010). The numbers of polyhedral graphs on 
, 2, ... in for which 
are given by 0, 0, 0, 0, 0, 1, 1, 3, 18, 129, ...
(E. Weisstein, Sep.3, 2024). These include stacked 3-prism graphs. Two additional
infinite families of such graphs were noted by Plummer and Toft (1987), the first
of which are known in this work as Plummer-Toft
graphs.
