Introducing Grünbaum’s Conjecture
March 10, 2023
Hi!
I would like to start by giving thanks to Dr. Fowler (external advisor) and Ms. Holloway (internal advisor) for agreeing to advise me on this project.
This is the first in a series of blogs in which I try to tackle Grünbaum’s Conjecture. In mathematics, graph colorings are studied for their wide range of uses in computer science, information theory, etc. and many problems in everyday life.
The Problem
Grünbaum first introduced the conjecture in 1968 at a conference as a generalization of the Four Colour Theorem. It is stated as follows: If a cubic graph has a polyhedral embedding on an orientable surface, then it is 3-edge colorable.
To better understand what this says, let’s introduce some definitions.
- Cubic Graph: A Graph In Which Every Vertex Has 3 Edges
- Edge-Coloring: A Coloring Of The Edges In Which No Two Incident Edges Have The Same Color (A 3-Edge Coloring Means Only Three Colorings Are Needed)
- Orientable Surface: A Surface With An “Inside” And “Outside” Like The Torus; Surfaces Like The Möbius Strip Are Non-Orientable
- Polyhedral Embedding: Intuitively Understood A “No-Crossing” Condition For The Edges (The Formal Definition Is That The Dual Graph Is Simple, Or That It Has No Loops Or Multiple Edges)
Current Research
We now know the conjecture is false in general, with counter-examples for non-orientable surfaces appearing in many places. Recently, Kochol constructed counter-examples for surfaces of genus at least 5 (visualized as a torus with 5 holes). However, the conjecture is still open for surfaces of lower genus.
Many approaches take advantage of the problem’s relationship with snarks, which are cubic graphs with no 3 edge-coloring. Then, to prove Grünbaum’s conjecture, one simply has to show that no snark has a polyhedral embedding on an orientable surface. This is the approach taken by Mohar, and he has proven the result for all snarks with up to 30 vertices using computer assistance.
Other approaches examine an equivalent formulation of the conjecture, which posits that every triangulation of surface has a Grünbaum coloring. A Grünbaum coloring is a different edge coloring scheme in which each all the faces of a graph are triangles and each edge of a face has a different color. The statement is then proven by examining the so-called dual graph obtained by drawing a vertex for each face and an edge for each pair of adjacent faces.
Currently, there are a couple partial solutions of the conjecture. Recently, Matsumoto et al. published a result proving that all even triangulations (ones where vertices had even degree) had Grünbaum colorings. In a different vein, Albertson et al. have shown that all triangulations with chromatic number not equal to 5 will have a Grünbaum coloring.
Next Steps
In the coming week, I hope to explore more about the current approaches that I have mentioned above. In particular, I have my eyes set on understanding some of the computer-based methods for checking snarks.
Feel free to leave any comments or questions below and see you next week!
Citations
- Albertson, M. O., Alpert, H., Belcastro, S. M., & Haas, R. (2010). Grünbaum Colorings Of Toroidal Triangulations. Journal Of Graph Theory, 63(1), 68-81.
- Kotrbčík, Michal & Matsumoto, Naoki & Mohar, Bojan & Nakamoto, Atsuhiro & Noguchi, Kenta & Ozeki, Kenta & Vodopivec, Andrej. (2017). Grünbaum Colorings Of Even Triangulations On Surfaces. Journal Of Graph Theory. 87. 10.1002/Jgt.22169.
- MOHAR, B., & VODOPIVEC, A. (2006). On Polyhedral Embeddings Of Cubic Graphs. Combinatorics, Probability And Computing, 15(6), 877-893. Doi:10.1017/S0963548306007607