47 votes

Generalizations of the four-color theorem

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 ...
43 votes
Accepted

Has there been a computer search for a 5-chromatic unit distance graph?

As of this morning there is a paper on the ArXiv claiming to show that there exists a 5-chromatic unit distance graph with $1567$ vertices. The paper is written by non-mathematician Aubrey De Grey (...
  • 565
39 votes
Accepted

Does there exist a graph with maximum degree 8, chromatic number 8, clique number 6?

Yes, it exists. Take 5 triangles $T_1,\dots,T_5$ (all 15 vertices are distinct) and draw also all edges between $T_i$ and $T_{i+1}$, $i=1,2,3,4$, and between $T_5$ and $T_1$. All degrees are equal to ...
  • 90.3k
34 votes
Accepted

Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946

I tried to go through Birkhoff and Lewis many years ago but it is not easy because they use different variables and the style is so different to modern proofs. In modern terms, the key idea is that ...
  • 11.3k
32 votes

Generalizations of the four-color theorem

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 ...
26 votes

Generalizations of the four-color theorem

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 ...
25 votes
Accepted

Smallest known counterexamples to Hedetniemi’s conjecture

Yes, Xuding Zhu did this in Relatively small counterexamples to Hedetniemi's conjecture (J. Comb. Theory B 146 (2021) pp. 141-150, doi:10.1016/j.jctb.2020.09.005, arXiv:2004.09028) where the sizes of ...
23 votes

Generalizations of the four-color theorem

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 ...
21 votes

Generalizations of the four-color theorem

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 ...
16 votes

Does there exist a graph with maximum degree 8, chromatic number 8, clique number 6?

Relevant footnotes to Fedor Petrov's nice, helpful, and completely correct answer. Fedor's answer seems essentially unimprovable both in brevity and completeness (it's all there). I hadn't expected ...
  • 5,833
15 votes
Accepted

Could the 4-color theorem be proven by contracting snarks?

Yes, the 4-colour theorem is true if and only if every snark is non-planar (this is due to Tait). Showing that a snark has a Petersen minor would be enough to show that it is non-planar.
  • 11.3k
15 votes
Accepted

Induced subgraphs of any given smaller chromatic number

Not necessarily. Komjáth showed that it is consistent that there is a graph of chromatic number $\aleph_2$ which does not have a subgraph (not just induced) of chromatic number $\aleph_1$. See P. ...
14 votes
Accepted

Graphs in which any two odd cycles have a common vertex

The claim on graphs without $K_5$ is a particular case of the (still open in general) Erdos--Lovasz Tihany conjecture. (Tihany is not a surname, but the name of a peninsula on Balaton lake in Hungary.)...
14 votes

Choosing two-colorable subgraph in a triangulation

Yes, such a subgraph always exist. Let $G$ be a planar triangulation. By the $4$-colour theorem, $G$ has a $4$-colouring. We let $H$ be the subgraph consisting of all edges with endpoints coloured $...
  • 29.1k
14 votes
Accepted

Does the existence of a unique chromatic (possibly transfinite) number for every (possibly non-finite) simple graph imply the axiom of choice?

It seems that your question has a positive answer, as shown by Galvin and Komjáth in their paper Galvin, F.; Komjáth, P., Graph colorings and the axiom of choice, Period. Math. Hung. 22, No.1, 71-...
  • 35.6k
13 votes

Is there any fast implementation of four color theorem in Python?

If you have have some specific, moderately large graphs that you want to color with four colors, you could try using a SAT solver. For each vertex $v$ and each integer $i\in \{1,2,3,4\}$, let $x_{v,i}...
  • 67.1k
12 votes

Generalizations of the four-color theorem

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 ...
12 votes
Accepted

Is this graph 3-colorable?

If I constructed the graph correctly, according to a program the chromatic number is $4$, so the graph is not 3 colorable. The program is: https://code.google.com/p/graphcol/ Got the same result ...
  • 23.5k
12 votes
Accepted

Berge-Fulkerson conjecture --- the planar case

The Berge-Fulkerson conjecture holds for planar graphs. Here is a proof. Let $G$ be a bridgeless cubic planar graph. The dual graph $G^*$ is a triangulation. By the Four Colour Theorem, $G^*$ has a ...
  • 29.1k
11 votes

Strengthening the induction hypothesis

Theorem (difficult): Every planar graph can have its edges directed such that the indegree of each vertex is $\leq 3$. Strengthening (easy): Every plane graph can have its edges directed such that ...
11 votes

Generalizations of the four-color theorem

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

Generalizations of the four-color theorem

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é." ...
11 votes
Accepted

What is known about graphs that permit only one colouring?

It's a bit hard to give a comprehensive answer without knowing exactly what sort of properties you are after, but here is a start. Such graphs are called uniquely colorable graphs (see here and here). ...
11 votes
Accepted

Coloring almost-disjointness

No, $\chi(G)=\mathfrak c$, in fact $G$ contains a complete subgraph on $\mathfrak c$ vertices. A simple way to construct one is by fixing a bijection $f\colon\Bbb Q\to\omega$ and fixing, for every $r\...
11 votes

Is there any fast implementation of four color theorem in Python?

Robertson, Sanders, Seymour and Thomas, who produced a more streamlined proof of the 4-colour theorem, also addressed the algorithmic question in the paper https://dl.acm.org/doi/pdf/10.1145/237814....
  • 11.3k
10 votes
Accepted

Coloring of the plane

Seems to be the polychromatic number of the plane. According to my knowledge, the value is at least 4 (due to Raiskii) and at most 6 (due to Stechkin). See Chap. 4 and 6 of The Mathematical Coloring ...
  • 2,469
10 votes
Accepted

A variant to the Hadwiger-Nelson problem

By considering all the rational numbers on the $x$-axis we can see that we need at least countably many colors. This is also sufficient, that is the chromatic number of the rational-distances graph is ...
10 votes
Accepted

Relationship of clique, independence, and chromatic numbers

I'll restrict attention to graphs on $n$ vertices and call your parameter $X$. The numerator is at least some multipe of $\log n$ by Ramsey's theorem, and the denominator is at most $n$, so $X \geq \...
  • 4,489
10 votes

Has there been a computer search for a 5-chromatic unit distance graph?

It depends how serious you require the search to be. ☺ When writing this note, I made a few attempts at experimenting in this direction, but I quickly came to the conclusion that either I didn't know ...
  • 23.1k
10 votes
Accepted

Hadwiger-Nelson problem for $\ell^\infty$

No. The set of all $\{0,1\}$-sequences is also a clique in $G$. Thus, $\chi(G) \geq 2^{\aleph_0}$. On the other hand, the set of all bounded real sequences has size $2^{\aleph_0}$, so $\chi(G)=2^{\...
  • 29.1k

Only top scored, non community-wiki answers of a minimum length are eligible