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.; Grigni, M.; and
Papadimitiou, C. "Planar Map Graphs." In Proc. 30th Symposium on Theory
Computing, pp. 514-523, 1998.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).
