## 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.