Grünbaum colorings extended to non-facial 3-cycles

sarah-marie belcastro, Ruth Haas


We consider the question of when a triangulation with a Grünbaum coloring can be edge-colored with three colors such that the non-facial 3-cycles also receive all three colors; we will call this a strong Grünbaum coloring. It turns out that for the sphere, every triangulation has a strong Grünbaum coloring, and that the presence of a K5 subgraph prohibits a strong Grünbaum coloring, but that K5 is not the only such barrier. We investigate the ramifications of these facts. We also show that for every other topological surface there exist triangulations with a strong Grünbaum coloring and triangulations that have Grünbaum colorings but that cannot have a strong Grünbaum coloring. Finally, we reframe strong Grünbaum colorings as certain hypergraph edge colorings, and raise the question of how many colors are needed to achieve an edge coloring such that both facial and non-facial 3-cycles receive three colors.


embedding, edge coloring, Grünbaum coloring, triangulation

Full Text:




M.O. Albertson, H. Alpert, s-m. belcastro, and R. Haas, Grunbaum colorings of toroidal tri-angulations, Journal of Graph Theory, 63:1 (2010), 68–81.

J. Balogh, P. Hu, B. Lidicky, F. Pfender, J. Volec, and M. Young, Rainbow triangles in threecolored graphs, Journal of Combinatorial Theory, Series B, 26 (2017), 83–113.

s-m. belcastro, Small snarks and 6-chromatic triangulations on the Klein bottle, Australasian J. Combinatorics, 65:3 (2016), 232–250.

M. Kasai, N. Matsumoto, and A. Nakamoto, Grunbaum colorings of triangulations on the projective plane, Discrete Applied Mathematics, 215 (2016), 155–163.

S. Lawrencenko and A.M. Magomedov, All face 2-colorable d-angulations are Grunbaum colorable, Journal of Combinatorial Mathematics and Combinatorial Computing, 95 (2015),


S. Lawrencenko, M.N. Vyalyi, and L.V. Zgonnik, Grunbaum coloring and its generalization to arbitrary dimension, Australasian Journal of Combinatorics, 67:2 (2017), 119–130.

R. Li, B. Ning, and S. Zhang, Color Degree Sum Conditions for Rainbow Triangles in EdgeColored Graphs, Graphs and Combinatorics, 32 (2016), 2001–2008.

B. Li, B. Ning, C. Xu, and S. Zhang, Rainbow triangles in edge-colored graphs, European Journal of Combinatorics, 36 (2014), 453–459.

G-H. Zhang and B. Skinner, Chromatic index of simple hypergraphs, Discrete Mathematics, 343:12 (2020), 112087.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats