## Coloring

### 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?**

## Hamiltonian cycles

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: generalizations-of-the-four-color-theorem.

You left off a condition in your equivalent statement of 4CT: should have been that every cubic *bridgeless* planar graph is 3-edge-colorable.

BTW, David, I was surprised never seeing before (or thinking before) this natural extension of the 4CT. Did you see it before?

It doesn’t look familiar to me, no.

A d-edge-coloring of a d-regular graph is a partition into perfect matchings, and well before the 4CT proof, cubic bridgeless (not necessarily planar) graphs were known to have perfect matchings (Petersen’s theorem). The corresponding result for higher dimensional polytopes follows from Balinski’s theorem together with theorem 4 of Naddef & Pulleyblank “Matchings in Regular Graphs” Discrete Math. 1981. So at least one obvious precondition for coloring is true.

Naddef & Pulleyblank, in the discussion following this theorem, bring up the 3-edge coloring formulation of the 4CT and talk about “polyhedral analogues” of it, but don’t make the step from there to higher dimensions.

Dear David, thanks! corrected –Gil

You also have to add the 3-connectivity assumption to Barnette conjecture I. I think it is Np-hard to test if a planar cubic bipartite graph is hamiltonian.

Dear Professor Kalai, thank you very much for the good collection of 4 CT related problems, I wonder if there is a collection of the progress of them.

Dear Bojan, David and rupeixu, indeed we should add “3-connected” both to Barnette conjecture and to Tait’s conjecture. I corrected it, thanks. Thanks for the further comments, David. I think that a collection of 4CT related problems and what is their status will make a good MathOverflow question. I am not aware of such a collection.

Another conjecture of Barnette (fixing Tait’s conjecture) states that cubic planar graphs with faces of size at most 6 are hamiltonian. This includes as a special case the “fullerene graphs” (cubic planar with faces of size 5 or 6). Some recent progress on this problem has been claimed:

http://arxiv.org/abs/1409.2440

An intriguing though not difficult connection between some of these ideas (due to Whitney) is that if a plane 3-valent 3-connected graph has a Hamiltonian circuit (HC) then it can be face colored with four or fewer colors. The idea for getting a 4-ccloring being to two-color the faces inside the HC and with two different colors to two-color the faces outside the HC.

Dear Drew and Joseph, thanks for the comments. Let me draw attention to the following post by David Eppstein on knots and links on graphs of 4-polytopes: http://11011110.livejournal.com/301197.html