# Tag Info

## Hot answers tagged graph-colorings

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

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

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

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

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

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

• 67.1k

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

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

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

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

• 4,489

### 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
### 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^{\...