Edge-coloring of simple polytopes
One of the equivalent formulation of the four-color theorem asserts that:
Theorem (4CT) : Every cubic bridgeless planar graph is 3-edge colorable
So we can color the edges by three colors such that every two edges sharing a vertex are colored by different colors.
Abby Thompson asked the following question:
Question: Suppose that G is the graph of a simple d-polytope with n vertices. Suppose also that n is even (this is automatic if d is odd). Can we always properly color the edges of G with d colors?
Vising theorem reminded
Vising’s theorem asserts that a graph with maximum degree D can be edge-colored by D+1 colors. This is one of the most fundamental theorems in graph theory. (One of my ambitions for the blog is to interactively teach the proof based on a guided way toward a proof, based on Diestel’s book, that I tried in a graph theory course some years ago.) Class-one graphs are those graphs with edge chromatic number equal to the maximum degree. Those graphs that required one more color are called class-two graphs.
Moving to triangulations
Thompson asked also a more general question:
Question: Let G be a dual graph of a triangulation of the (d-1)-dimensional sphere. Suppose that G has an even number of vertices. Is G d-edge colorable?
Grunbaum’s question and counterexample
Branko Grunbaum proposed a beautiful generalization for the 4CT: He conjectured that the dual graph of a triangulation of every two-dimensional manifold is 3-edge colorable. This conjecture was refuted in 2009 by Martin Kochol.
Triangulations in higher dimensions
A third question, even more general, posed by Thompson is: Let G be a dual graph of a triangulation of a (d-1)-dimensional manifold, d ≥ 4. Suppose that G has an even number of vertices. Is G d-edge colorable?
Coloring graph is notoriously difficult but finding a Hamiltonian cycle is even more difficult.
Tait’s conjecture and Barnette’s conjectures
Peter Tait conjectured in 1884 that every 3-connected cubic planar graph is Hamiltonian. His conjecture was disproved by William Tutte in 1946. A cubic Hamiltonian graph must be of class I and therefore Tait’s conjecture implies the 4CT. David Barnette proposed two ways to save Tait’s conjecture: one for adding the condition that all faces have an even number of edges or, equivalently that the graph is bipartite, and another, by moving up in the dimension.
Barnette’s conjecture I: Planar 3-connected cubic bipartite graphs are Hamiltonian.
Barnette’s conjecture II: Graphs of simple d-polytopes d ≥ 4 are Hamiltonian.
Barnette’s hamiltonicity conjecture in high dimension does not imply a positive answer to Thompson’s quaestion. We can still ask for the following common strengthening: does the graph of a simple d-polytope, d ≥ 4, with an even number of vertices contain [d/2] edge-disjoint Hamiltonian cycles?
There are few more things to mention: Peter Tait made also three beautiful conjectures about knots. They were all proved, but it took a century more or less. When we move to high dimensions there are other notions of coloring and other generalizations of “Hamiltonian cycles.” You can Test Your Imagination and try to think about such notions!
Update (Dec 7): Following rupeixu’s comment I asked a question over mathoverflow: generalizations-of-the-four-color-theorem.