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

Community wiki

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

Community wiki

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

Community wiki

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

- 82.5k

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

Community wiki

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

Community wiki

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

- 166

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

- 19.2k

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

Community wiki

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

Community wiki

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

Community wiki

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

Community wiki

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

- 82.5k

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

- 2,109

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

- 82.5k

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

#### Related Tags

graph-colorings × 570graph-theory × 481

co.combinatorics × 300

hypergraph × 47

reference-request × 38

infinite-combinatorics × 32

algorithms × 28

set-theory × 27

computational-complexity × 23

extremal-graph-theory × 20

discrete-geometry × 19

ramsey-theory × 17

matching-theory × 14

perfect-matchings × 10

cayley-graphs × 10

combinatorial-optimization × 9

chromatic-polynomial × 9

bipartite-graphs × 8

graph-minors × 8

lo.logic × 7

pr.probability × 6

directed-graphs × 6

gr.group-theory × 5

mg.metric-geometry × 5

polynomials × 5