# Generalizations of the Four-Color theorem

The four color theorem asserts that every planar graph can be properly colored by four colors.

The purpose of this question is to collect generalizations, variations, and strengthenings of the four color theorem with a description of their status.

(Motivated by a comment of rupeixu to a recent blog post on my blog presenting a question by Abby Thompson regarding a natural generalization of the 4CT.) Related question:Generalizations of Planar Graphs .

• One basic source is: "The Four-color Problem: Assaults and Conquest" by Saaty and Kainen. It contains so many nice reformulations (over 120!). Could be useful to "parallel" a generalization. – Jérôme JEAN-CHARLES Dec 9 '14 at 22:56

One of the most important generalizations of the four color theorem is Hadwiger's conjecture. The Hadwiger conjecture asserts that a graph without a $K_{r+1}$ minor is $r$-colorable. There is a further generalization called the Weak Hadwiger Conjecture.

It is known that the Hadwiger conjecture is false for graphs with infinite chromatic number (consider the disjoint union of $K_n$ where $n\in\mathbb{N}$), whereas the Weak Hadwiger conjecture is true for those graphs (see this paper).

An interesting question is whether the Weak Hadwiger conjecture implies the Hadwiger conjecture for finite graphs.

The coloring of higher dimensional ball packings.

A ball packing is a collection of balls with disjoint interiors. The tangency graph of a ball packing takes the balls as vertices and connect two vertices if and only if they are tangent. Planar graphs are the tangency graphs of 2-dimensional disk packings. So the following is a generalization of four-color theorem.

Question: what is the maximum chromatic number $\chi_d$ for the tangency graph of a ball packing in dimension $d$?

I believe that everyone can prove that $\chi_d\le\kappa_d+1$ where $\kappa_d$ is the kissing number. The question was asked by Bagchi and Datta (2012) who gave the trivial lower bound $\chi_d\ge d+2$.

As far as I know, Maehara (2007) first attack the problem for dimension $3$. His construction for lower bound uses Moser spindle. It generalizes to higher dimensions and gives $\chi_d\ge d+3$.

The problem has also been asked on MO. One result is an answer of Cantwell. It uses halved cubes. It can be generalized to higher dimensions by a result of Liniail, Mishulam and Tarsi (1988) and gives $\chi_d\ge d+4$ for infinitely many $d$.

So the current status is: $d+4\le\chi_d\le\kappa_d+1$. There is a large gap in between.

update: I just improve the lower bound by constructing a unit ball packing in dimension $q^3-q^2+q$ with chromatic number $q^3+1$ where $q$ is a prime power. There are many other ball packings with high chromatic number, see this answer. The gap is still very large.

• Is it known whether this is the same as the chromatic number of maps whose regions are convex subsets of $\mathbb{R}^d$? – Noah Schweber Dec 8 '14 at 1:05
• @NoahS, This could be arbitrarily high, isn't it? – Hao Chen Dec 8 '14 at 8:09
• @NoahS Yes, it's arbitrarily high. See arxiv.org/abs/math/0106095 . So it is known that they are not the same. – Hao Chen Dec 8 '14 at 8:17

Here are two:

Recall that the four colour theorem is equivalent to the statement that bridgeless cubic planar graphs are three-edge-colourable.

There is Tutte’s three-edge-colouring conjecture that every cubic bridgeless graph not containing the Petersen graph as a minor is 3-edge-colourable. This is a theorem now.

A (still open) generalization of this is Tutte’s 4-flow conjecture that every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow.

Another is a conjecture of Seymour about $d$-regular planar (multi-)graphs. This says that every $d$-regular planar graph which satisfies the natural cut condition (for every odd-cardinality subset $X$ of the vertices there are at least $d$ edges between $X$ and the complement) is $d$-edge-colourable. This is still open in general but known for values of $d \leq 8$ (see here).

The chromatic polynomial of any planar graph has no real roots that are greater than or equal to four.

Note that the four color theorem says that 4 cannot be a root, and it's well known that the roots can't be real numbers greater than or equal to 5.

• Is it possible that $\chi_G(x+4)$ has positive coefficients? I looked through the table of chromatic polys. of triangulations in Birkhoff-Lewis up to 19 vertices, and found no counterexamples. – Ian Agol Jun 16 '15 at 13:43
• Ian: This paper claims real roots arbitrarily close to 4: link.springer.com/article/10.1007/… – Geoffrey Irving Apr 30 '16 at 6:04

Kronheimer and Mrowka recently defined an instanton invariant of embedded trivalent graphs (webs) in $$\mathbb{R}^3$$. This can be regarded as (roughly) counting the number of representations of the fundamental group of the complement of the graph to $$SO(3)$$ such that the meridian of each edge is sent to an involution. They conjecture that for planar webs their invariant gives the number of Tait colorings (it's easy to see that a Tait coloring gives a representation of this sort to the Klein four group). They show this is true for Eulerian planar trivalent graphs among others. They show that their invariant is always non-zero, and hence this conjecture implies the four color theorem. They also give various refinements of this conjecture in this paper and a sequel. See also this blog-post.

Let me mention here Thompson's three questions:

Question 1: 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?

Question 2 : 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?

Question 3: Let $G$ be a dual graph of a triangulation of a $(d-1)$-dimensional manifold, $d \ge 4$. Suppose that $G$ has an even number of vertices. Is $G$ $d$-edge colorable?

Questions 1 and 2 coincides (by Steinitz's theorem) for $d=3$ and are equivalent there to the 4CT.

The starting point for these questions is a beautiful generalization for the 4CT proposed by Branko Grunbaum:

Grunbaum's conjecture: The dual graph of a triangulation of every two-dimensional manifold is alwayas 3-edge colorable.

Grunbaum's conjecture was disproved in 2009 by Martin Kochol.

One generalization with a spectral graph theory flavor is the Colin de Verdière Conjecture, originating in

Colin de Verdière, Yves. "Sur un nouvel invariant des graphes et un critere de planarité." Journal of Combinatorial Theory, Series B 50, no. 1 (1990): 11-21. Journal link (English translation in this volume)

For a graph $G$ with $n$ vertices, consider an $n\times n$ symmetric matrix $M$ satisfying:

• For every $i\neq j$, $M_{ij} < 0$ if $\{i,j\}$ is an edge in $G$, and $M_{ij} = 0$ otherwise.

(This looks a bit like a generalization of the usual graph Laplacian matrix.)

The smallest eigenvalue of $M$ must (by Perron-Frobenius) have multiplicity equal to the number of connected components of $G$. So what about the multiplicity of the second smallest eigenvalue? Now this may depend on the choice of $M$, so let's consider its maximum over all such matrices $M$.

Since the diagonal of $M$ is unconstrained, we may assume that this second-smallest eigenvalue is $0$. Then we're asking about the largest possible corank of such a matrix $M$.

Finally, require of $M$ a sort of nondegeneracy condition, called the Strong Arnold Property:

• Within the space of $n\times n$ real symmetric matrices, the submanifold comprising those that satisfy the bulleted condition above and that comprising those with the same rank as $M$ intersect transversally at $M$.

(A theorem of van der Holst, Lovász and Schrijver gives an equivalent algebraic condition: The only symmetric matrix $X$ with $MX=0$ that is zero on the diagonal and on the edges of $G$ is $X=0$.)

The largest corank of a matrix $M$ satisfying both of the bulleted conditions above is the Colin de Verdière number of $G$, denoted $\mu(G)$. This parameter has some nice properties, e.g., it is monotonic with respect to graph minors.

Most remarkably, Colin de Verdière showed that $\mu(G) \le 3$ if and only if $G$ is planar (and that $\mu(G) \le 2$ iff $G$ is outerplanar) and put forward

The Colin de Verdière Conjecture:   $\chi(G) \le \mu(G)+1$

Currently, the conjecture is known to hold for $\mu(G) \le 4$. This relies on current proofs of the 4-color theorem, of course, although a direct proof of the conjecture could conceivably offer a very different route to that result.

ADDED: Colin de Verdière showed $\mu(G)=n-1$ iff $G=K_n$. (This seems obvious, but does require checking the Strong Arnold Property.) Together with the minor-monotonicity mentioned above, this shows that the conjecture would follow as a special case of the Hadwiger Conjecture, as pointed out here in a comment by Gil Kalai. This is also noted by Colin de Verdière himself upon stating the conjecture!

• Dear Lois, thanks for the answer! It is worth mentioning that the Hadwiger conjecture implies the Colin-de-Verdiere conjecture (I think). – Gil Kalai Sep 19 '15 at 17:33
• @GilKalai: Good point. I added the details. – Louis Deaett Sep 19 '15 at 22:27

There is a recent generalization to $k$-uniform hypergraphs that are embeddable in $\mathbb{R}^d$ without edge intersections. "For $k=d=2$ the problem specializes to graph planarity":

Carl Georg Heise, Konstantinos Panagiotou, Oleg Pikhurko, Anusch Taraz. "Coloring $d$-embeddable $k$-uniform Hypergraphs." Discrete & Computational Geometry (2014) 52:663-679. (arXiv abs link.)

"We say that $H = (V, E)$ is a $k$-uniform hypergraph if the vertex set $V$ is a finite set and the edge set $E$ consists of $k$-element subsets of $V$."

There are also interesting weak forms of the 4CT where the challenge is of course to give a direct proof. An immediate consequence of the 4CT is that every planar graph has an independent set of size $n/4$, the best known result (without using 4CT) is $2n/9$ by Albertson (1976). It is very interesting to ask about fractional coloring number. Hilton, Rado, and Scott, introduced the notion of fractional coloring and proved "A (< 5)-colour theorem for planar graphs (1973)."

We say that a graph $G$ have a fractional coloring number $t$ $(\chi^*(G)=t)$ if we can assign the independent sets of $G$ nonnegative weights such that the sum of weights of independent sets containing any given vertex is at most 1 and the total sum of weight is $t$, and, moreover, $t$ is the smallest number with this property.

Two remarkable conjectures by Heckman and Thomas are:

Conjecture 1: Every subcubic triangle-free graphis fractionally 14/5-colorable.

Conjecture 2: Every subcubic triangle-free planar graph is fractionally 8/3-colorable.

(So conjecture 1 is a strengthening of a weakening of the 4CT.)

in 2013, Dvořák, Sereni, and Volec in the paper Subcubic triangle-free graphs have fractional chromatic number at most 14/5 proved Conjecture 1!

Consider a graph $\Gamma$ embedded on a surface $\Sigma$. Is there a finite-sheeted cover $\tilde{\Sigma}$ of $\Sigma$ so that the induced cover $\tilde{\Gamma}$ of $\Gamma$ is 4-colorable? We know that the cover of $\Gamma$ induced by the universal cover of $\Sigma$ is 4-colorable (as is any planar cover) by the 4-color theorem, so one way to describe the question is can one make the universal cover of $\Sigma$ have a 4-coloring of the induced graph which is invariant under a finite-index subgroup of the covering translations?

For any graph, one can always take a finite cover which is bipartite, and this can also be arranged by an induced cover of an embedding in a surface. So the point of the question is to deal with the given embedding. Maybe a more natural way to phrase the question is to color a map on a surface. I'm not sure if this question has been posed before, so I don't have any references.

• Dear Ian, Very nice question! if we start with an embedding of the complete graph like $K_6$ on $RP^2$ or $K_7$ on the torus can we find such a cover? – Gil Kalai Sep 11 '16 at 15:54
• @GilKalai: The question is trivial for graphs in $\mathbb{RP}^2$, since a 2-fold cover will be planar. For $K_7$ on the torus, notice that it is a valence 6 triangulation. Thus, it is commensurable with a triangulation of the torus with 4 vertices which is 4 colorable (the 4-fold cover of the 1-vertex triangulation), and hence it has a 4-colorable cover. – Ian Agol Sep 11 '16 at 17:12
• "it is a valence 6 triangulation. Thus, it is commensurable with a triangulation of the torus with 4 vertices " Ian, I dont understand it but maybe I miss something basic. Does this argument extend to other $K_n$'s on surfaces of higher genus? – Gil Kalai Sep 11 '16 at 18:22
• @GilKalai: It might extend some times. Regular triangulations of surfaces are all commensurable. So if a $K_n$ has an embedding as a triangulation in a surface, and one can find a regular triangulation of degree $n-1$ which is 4-colorable, then the $K_n$ embedding is virtually 4-colorable by commensurability. However, I'm not sure which $K_n$'s embed as regular triangulations on a surface. More generally, one could try to answer the question for regular cellulations of surfaces (where all faces and vertices have the same degree). – Ian Agol Sep 11 '16 at 22:09
• I can answer the question now for tori. Take a map on a torus (thought of as a cell structure), and a simple closed non-trivial curve in the 1-skeleton. Take the infinite cyclic cover dual to this curve (so cut along the curve to get an annulus, and glue infinitely many copies of this annulus end-to-end). Then the map on the infinite cyclic cover is 4-colorable, since it is planar. But there are only finitely many colorings of the annuli, and there must be two distinct curves which have the same adjacent colorings. Then cut and glue along these curves to obtain a compact 4-colored torus. – Ian Agol Sep 12 '16 at 21:52

Each planar graph is 5-choosable (Thomassen, 1995).

• But, there are planar graphs that are not 4-choosable (incidentally, I think the smallest known example is due to recent Fields' medalist Maryam Mirzakhani), so this generalization is false. – Tony Huynh Dec 8 '14 at 1:14
• ...who found it in 1996, when she was 19 years old. – Delio Mugnolo Dec 8 '14 at 8:54
• well, it was not meant as a generalization. while it is known that the chromatic number gives a lower bound for the choosability number, the choosability number cannot be bounded from above by a function of the chromatic number, so they are indeed two different objects. i mentioned thomassen's theorem simply as a related result. – Delio Mugnolo Dec 8 '14 at 8:59

6 colors for a Klein bottle, 7 for a torus. How about higher dimensional manifolds?

• I guess that you mean that a (cartographic) map on a Klein bottle is colorable by 6 colors, etc. This is mentioned (and generalized) in the Wikipedia article: en.wikipedia.org/wiki/Four_color_theorem#Generalizations – Todd Trimble Dec 8 '14 at 3:36
• Indeed so. How about if each country may consist of n disjoint regions? – william rood Dec 8 '14 at 8:51
• $K_{7}$ in the torus has a nice algebraic description: Start with the graph formed by the Eisenstein integers, where $a$ is adjacent to $b$ means $|a-b| = 1$. Every vertex of this graph has degree 6, and it's planar. To make the plane a torus, we quotient by a lattice. To make this well-defined for how we identify vertices and edges, that lattice has to be an ideal. Choose an ideal of norm 7, like $(2+\sqrt{-3})$, and we now have 7 vertices (all have degree 6), yielding $K_{7}$. I don't know if replacing the Eisenstein ring with structures like the Hurwitz ring gives nice generalizations. – DavidLHarden Dec 9 '14 at 20:14
• The problem is only interesting for surfaces because every graph can be embedded in a manifold of dimension 3 or higher. – Matt Samuel Dec 18 '14 at 20:46

Let $P$ be a $d$-dimensional polytope with $n$ vertices. For every $2$-dimensional face $F$ triangulate $F$ by non crossing diagonals. So if $F$ has $k$ sides you add $(k-3)$ edges. It is known that the total number of edges you get , denoted by $f^{\bf +}_1(P)$ (including the original edges of the polytope) satisfies the inequality $$f_1^{\bf +}(P) \ge dn - {{d+1} \choose {2}}.$$

A polytope is called elementary if equality holds:

$$f_1^{\bf +}(P) = dn - {{d+1} \choose {2}}.$$

It is known that If $P$ is elementary so is its dual $P^*$.

We can consider the following classes of graphs:

1) $E_d$ = Graphs of elementary $d$-polytopes and all their subgraphs

2) $F_d$ = Graphs obtained by elementary $d$-polytopes by triangulating all 2 faces by non crossing diagonals, and all their subgraphs.

For $d=3$ both classes are the class of planar graphs.

Conjecture (weak) Graphs in $E_d$ are $(d+1)$-colorable.

Conjecture (strong) Graphs in $F_d$ are $(d+1)$-colorable.

Remarks: We can start instead of polytopes by arbitrary polyhedral $(d-1)$-dimensional pseudomanifolds. But it is conjectured that with such extensions we will not get new elementary objects.

The stronger generalization from the comment above.

• Assign a trianglenumber of $+1$ or $-1$ to each triangle of a maximal planar graph with $v$ vertices and make all $2^{2(v-2)}$ different variations.

• For every variation define the vertexnumbers by making the sum $\mod 3$ of the trianglenumbers for all the triangles incident to each vertex. The vertices have now a vertexnumber of $0$, $1$ or $2$.

Conjecture 1: The number of different variations of vertexnumbers for $v-2$ vertices is equal to $3^{v-2}$ if the two missing vertices are adjacent.

Corollary: Then there is also a proper vertexnumbering (all vertexnumbers=0) for this $v-2$ vertices. It is easy to prove then that the two missing vertices have also a vertexnumber=0. The maximal planar graph is then $4$-colorable.

The number of different variations of vertexnumbers for ALL vertices is more than $3^{v-2}$ except if all vertices have even degree (the graph is then 3-vertex-colorable).

Conjecture 2: The number of different variations of vertexnumbers for $v$ vertices is equal to $3^{v-2}$ if all vertices have even degree.

Understanding conjecture 2 can help to better understand conjecture 1.

• Based on Heawood vertex character for the dual of cubic graphs. See C3 p.120 "The Four-color Problem: Assaults and Conquest" by Saaty and Kainen Dover Publications 1986. – patrick labarque Jan 9 '17 at 12:58
• See related conjectures here: sciencedirect.com/science/article/pii/… – Ian Agol May 28 '17 at 5:18
• Is there a reference for these conjectures? – Gjergji Zaimi Jun 18 '18 at 18:44
• "the comment above", for some value of "above". – Gerry Myerson Jun 20 '18 at 21:25
• @GerryMyerson I checked that reference and it only had standard facts about Heawood colorings etc. Patrick's conjecture seems pretty natural, but I haven't seen it in print before. – Gjergji Zaimi Jun 21 '18 at 1:38

A theorem of Grotzsch from 1959 asserts that every planar graph not containing a triangle is 3-colorable. This was reproved by Thomassen in "A short list color proof of Grotzsch’s theorem", J. Combin. Theory B, vol 88 (2003), 189–192.

Consider a finite family of non-overlapping circles. We can ask what is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors? By Koebe’s circle packing theorem (see this recent post) this is precisely the four color theorem so the answer is 4.

This observation suggests various generalizations and variations. See this post for quite a few of them. If you insist on unit circles but drop the condition "non-overlapping" you get Nelson's famous question about the chromatic number of the plane. Here are two questions.

1) Consider a finite family of circles such that every point in the plane is included in at most two circles. What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors?

Ringel’s circle conjecture (see this paper by Jackson and Ringel) asserts that the number of colors is bounded. (There is an example that five colors are required.)

2) Consider a finite family of pseudocircles. Here every pseudocircle is a closed simple path and two pseudocicles are either disjoint or hace two crossing points. Two pseudocircles are adjacent if the lens described by them does not contain any point from any other pseudocircle. What is the minimum number of colors needed to color the pseudocircles so that adjacent pseudocircles are colored with different colors? (In particular, is this number finite?)

An algebraic reformulation: Given the table of two ternary numbers of order 1 with two figures:

21

12

We do the following operation: We replace in one column each figure with the two other ones, in the two different ways to make the next tables of order 1+1=2. We get then two tables with four ternary numbers of order 2 with 3 figures.

Operation on the 1st column:

011

101

022

202

Operation on the 2nd column:

202

220

101

110

We can continue for order n, and get then: n! tables with 2^n different ternary numbers each with n+1 figures. Proving that each table of some order has always at least two ternary numbers in common with any other table of the same order is one more generalization of the FCT. Here the two tables have 101 and 202 in common. Add a 0 to the right of every number in every table to see the relation with the illustration below.

Illustration of the operations above:

• Add a 0 to the right of every number in every table. Then each table gives the different edge colorings (dual Tait coloring) for the boundary of a triangulated planar polygon with color 0 as fixed base color. The first table is for a triangle and an ear is added with each operation. Combination of two idem colored polygons gives a proper edge colored hamiltonian maximal planar graph. A much stronger generalization is the conjecture in mathoverflow.net/questions/258830/… – patrick labarque Jan 9 '17 at 8:49
• Sorry too convoluted for me. Could not you add at least a sketchy explanation of why exactly is this equivalent to the four color problem? – მამუკა ჯიბლაძე Jan 9 '17 at 21:42
• See the image I added (but can't see it). – patrick labarque Jan 10 '17 at 11:16
• Thank you! Not that I understand everything but it is certainly more than before :D I've made it visible, if you don't mind (if you do, just tell me and I will revert it back) – მამუკა ჯიბლაძე Jan 10 '17 at 11:23