where
is the maximum number of vertices incident with a graph
face (the maximum face degree). The conjecture is an important extension of the
four-color theorem and becomes a theorem in
the case of a facially complete planar
embedding (Chen et al. 1998, Tilley et al. 2025).
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.Chen, Z.-Z.; Grigni, M.;
and Papadimitriou, C. H. "Planar Map Graphs." In Proc. 30th Annual
ACM Symposium on Theory of Computing (STOC '98), Dallas, TX, May 23-26, 1998.
(Ed. J. S. Vitter). New York: ACM, pp. 514-523, 1998. https://doi.org/10.1145/276698.276865.Plummer,
M. D. and Toft, B. "Cyclic Coloration of 3-Polytopes." J. Graph
Th.11, 507-515, 1987.Tilley, J.; Wagon, S.; and Weisstein,
E. "A Catalog of Facially Complete Graphs." Util. Math.124,
157-169, 2025. https://doi.org/10.61091/um124-10.
of a planar embedding
satisfies
is the maximum number of vertices incident with a graph
face (the maximum face degree). The conjecture is an important extension of the
four-color theorem and becomes a theorem in
the case of a facially complete planar
embedding (Chen et al. 1998, Tilley et al. 2025).
