63
$\begingroup$

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 .

Improve this question
$\endgroup$
2
  • 8
    $\begingroup$ 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. $\endgroup$
    – Jérôme JEAN-CHARLES
    Commented Dec 9, 2014 at 22:56
  • 1
    $\begingroup$ mathoverflow.net/questions/273120/… is more about statements equivalent to the Four Color Theorem than about "generalizations, variations, and strengthenings," but still might be of some interest here. $\endgroup$
    – Gerry Myerson
    Commented May 19, 2021 at 6:05

19 Answers 19

Reset to default
47
$\begingroup$

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.

Improve this answer
$\endgroup$
32
$\begingroup$

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.

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

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

Improve this answer
$\endgroup$
24
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 10
    $\begingroup$ 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. $\endgroup$
    – Ian Agol
    Commented Jun 16, 2015 at 13:43
  • $\begingroup$ Ian: This paper claims real roots arbitrarily close to 4: link.springer.com/article/10.1007/… $\endgroup$
    – Geoffrey Irving
    Commented Apr 30, 2016 at 6:04
  • $\begingroup$ "and it's well known that the roots can't be real numbers greater than or equal to 5." - I guess you rather mean "and it's well known that the roots can't be natural numbers greater than or equal to 5." $\endgroup$
    – Nubok
    Commented Mar 20 at 23:31
  • 1
    $\begingroup$ @Nubok: No, I meant real numbers. See this blog post and Greg Kuperberg's comment. There's a skein theory argument where you can rewrite the chromatic polynomial for small faces as a sum of simpler terms with positive coefficients so long as x > 5. $\endgroup$
    – Noah Snyder
    Commented Mar 21 at 19:10
22
$\begingroup$

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.

Improve this answer
$\endgroup$
12
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Gil Kalai
    Commented Sep 11, 2016 at 15:54
  • 1
    $\begingroup$ @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. $\endgroup$
    – Ian Agol
    Commented Sep 11, 2016 at 17:12
  • $\begingroup$ "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? $\endgroup$
    – Gil Kalai
    Commented Sep 11, 2016 at 18:22
  • 1
    $\begingroup$ @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). $\endgroup$
    – Ian Agol
    Commented Sep 11, 2016 at 22:09
  • 5
    $\begingroup$ 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. $\endgroup$
    – Ian Agol
    Commented Sep 12, 2016 at 21:52
11
$\begingroup$

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.

Improve this answer
$\endgroup$
11
$\begingroup$

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!

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Dear Lois, thanks for the answer! It is worth mentioning that the Hadwiger conjecture implies the Colin-de-Verdiere conjecture (I think). $\endgroup$
    – Gil Kalai
    Commented Sep 19, 2015 at 17:33
  • $\begingroup$ @GilKalai: Good point. I added the details. $\endgroup$
    – Louis Deaett
    Commented Sep 19, 2015 at 22:27
8
$\begingroup$

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!

Improve this answer
$\endgroup$
8
$\begingroup$

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$."

Improve this answer
$\endgroup$
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 7
    $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Commented Dec 8, 2014 at 1:14
  • 6
    $\begingroup$ ...who found it in 1996, when she was 19 years old. $\endgroup$
    – Delio Mugnolo
    Commented Dec 8, 2014 at 8:54
  • $\begingroup$ 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. $\endgroup$
    – Delio Mugnolo
    Commented Dec 8, 2014 at 8:59
4
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ 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 $\endgroup$
    – Todd Trimble
    Commented Dec 8, 2014 at 3:36
  • $\begingroup$ Indeed so. How about if each country may consist of n disjoint regions? $\endgroup$
    – william rood
    Commented Dec 8, 2014 at 8:51
  • $\begingroup$ $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. $\endgroup$
    – DavidLHarden
    Commented Dec 9, 2014 at 20:14
  • 9
    $\begingroup$ The problem is only interesting for surfaces because every graph can be embedded in a manifold of dimension 3 or higher. $\endgroup$
    – Matt Samuel
    Commented Dec 18, 2014 at 20:46
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – patrick labarque
    Commented Jan 9, 2017 at 12:58
  • 1
    $\begingroup$ See related conjectures here: sciencedirect.com/science/article/pii/… $\endgroup$
    – Ian Agol
    Commented May 28, 2017 at 5:18
  • $\begingroup$ Is there a reference for these conjectures? $\endgroup$
    – Gjergji Zaimi
    Commented Jun 18, 2018 at 18:44
  • $\begingroup$ "the comment above", for some value of "above". $\endgroup$
    – Gerry Myerson
    Commented Jun 20, 2018 at 21:25
  • $\begingroup$ @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. $\endgroup$
    – Gjergji Zaimi
    Commented Jun 21, 2018 at 1:38
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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

  1. 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?)
Improve this answer
$\endgroup$
0
2
$\begingroup$

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:

enter image description here

Improve this answer
$\endgroup$
8
  • $\begingroup$ Fantastic! Do you have a reference to read more about this? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jan 8, 2017 at 8:55
  • $\begingroup$ 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/… $\endgroup$
    – patrick labarque
    Commented Jan 9, 2017 at 8:49
  • $\begingroup$ 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? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jan 9, 2017 at 21:42
  • $\begingroup$ See the image I added (but can't see it). $\endgroup$
    – patrick labarque
    Commented Jan 10, 2017 at 11:16
  • $\begingroup$ 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) $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jan 10, 2017 at 11:23
2
$\begingroup$

Another nice formulation is the following: Prove that the vertices of a MPG (all faces are triangles) without crossing diagonals can be put on a integer unit grid, so that NO triangle has an integer area (= xx.5).

Example: An illustration for $K4$ enter image description here

Answer by P. Labarque

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Can you please elaborate? $\endgroup$
    – Gil Kalai
    Commented Feb 28, 2021 at 15:07
  • 1
    $\begingroup$ Give the vertices on the grid crossings folowing colours: odd-odd=1, odd-even=2, even-odd=3 and even-even=4. $\endgroup$
    – P.Labarque
    Commented Feb 28, 2021 at 15:29
  • 1
    $\begingroup$ You should be able to edit this answer so that the image is included in it, rather than post it in a separate answer, which would make things clearer. It would also be helpful to add some more details: What is an MPG? What exactly is the relationship of this to the four-color theorem? Your argument seems to suggest it is a weakening, not a strengthening. $\endgroup$
    – Will Sawin
    Commented Feb 28, 2021 at 15:56
  • 1
    $\begingroup$ Pick's Theorem can be used here to calulate the areas. $\endgroup$
    – P.Labarque
    Commented Feb 28, 2021 at 18:49
  • 3
    $\begingroup$ Is this a generalization? $\endgroup$
    – András Bátkai
    Commented Feb 28, 2021 at 18:57
2
$\begingroup$

Closely related conjectures are the following: An acyclic colouring of a graph is a colouring of its vertices so that the subgraph spanned on union of every two colour classes is acyclic (a forest). Grunbaum conjectured in 1973 that every planar graph has acyclic colouring with five colours. This was proved by Borodin in 1976 who further conjectured that five colours always suffice with the additional condition that the union of every $k$ colour classes, $1 \le k \le 4$ induces a $(k-1)$-degenerate graph.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .