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