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

Abstract

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 K₅ subgraph prohibits a strong Grünbaum coloring, but that K₅ 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.