45

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

42

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 (of anti-aging fame), but it appears to be a serious paper. Time will tell if it holds up to scrutiny.
EDIT: in fact, it must be the one with 1585 vertices, ...

39

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 8, maximal clique is formed by two neighboring triangles, and $\chi=8$. Indeed, each color may appear at most twice (in at most two triangles), thus 7 colors ...

answered Oct 18 '17 at 12:01

Fedor Petrov

81.9k88 gold badges191191 silver badges346346 bronze badges

36

To answer the question it is important to disentangle the proof as follows.
Theorem 1. Every minimum counterexample to the 4CT is an internally 6-connected triangulation.
Theorem 2. If $T$ is a minimum counterexample to the 4CT, then no good configuration appears in $T$.
Theorem 3. For every internally 6-connected triangulation $T$, some good ...

34

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 if a graph contains a vertex $v$ of degree k, then you can get an expression of the form
$$P(G,\lambda) = (\lambda-k) P(G-v,\lambda) + \text{other terms}$$
where ...

32

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

28

The answer to both questions is "yes", by the De Bruijn–Erdős theorem.

answered Dec 15 '13 at 2:25

Nathaniel Johnston

4,27711 gold badge2626 silver badges2828 bronze badges

28

Since nobody seems to have addressed question 3, I will. The proofs of the 4-colour theorem are effective in the sense that they can be turned into polynomial-time algorithms. So there are no planar graphs for which 4-colouring is hard.

answered May 30 '14 at 23:22

Brendan McKay

32.9k22 gold badges6666 silver badges127127 bronze badges

25

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

24

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 the graphs are $3403$ and $10501$.
Marcin Wrochna has a preprint, Smaller counterexamples to Hedetniemi's conjecture, arXiv:2012.13558, that brings the sizes ...

22

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.

21

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

19

If you choose $p_G$, $q_G$ and $r_G$, such that $p_G>\Delta~q_G>\Delta^2~r_G>0$, (with $\Delta=\Delta(G)$), then your question is equivalent to "neighbor distinguishing colorings by multisets".
As far as I know, the best known bound for this problem is proved here:
L. Addario-Berry, R. E. L. Aldred, K. Dalal, and B. A. Reed. Vertex colouring
edge ...

19

If $n\mapsto\Gamma_n$ is a function that on input $n$ produces a graph of size $n$ in time polynomial in $n$, its range is a sparse polynomial-time set, meaning that it contains only polynomially many (actually, at most $1$ in this case) elements of any given size. Thus, if $n$ is given in unary, the set $X$ of pairs $(n,c)$ such that $\Gamma_n$ is $c$-...

answered May 30 '14 at 15:48

Emil Jeřábek

36.9k33 gold badges118118 silver badges176176 bronze badges

16

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 such an elegant solution to exist, rather looked in the more complicated directions like sparse or dense random graphs, random regular graphs, and general ...

15

As the other answer indicates, the yes answer to your question is known as the De Bruijn-Erdős theorem.
This holds regardless of the size of the graph. The De Bruijn–Erdős theorem is a particular instance of what in combinatorics we call a compactness argument or Rado's selection principle, and its truth can be seen as a consequence of the topological ...

answered Dec 16 '13 at 2:13

Andrés E. Caicedo

30.2k55 gold badges112112 silver badges199199 bronze badges

15

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.

15

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. Komjáth, Consistency results on infinite graphs, Israel J. Math., 61 (1988), pp. 285-294.

14

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.)
This particular case has been proved in W.G. Brown and H.A. Jung, On odd circuits in chromatic graphs, Acta Math. Acad. Sci. Hungarica, V. 20(1), pp. 129-134....

14

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 $1$ and $2$, or with endpoints coloured $3$ and $4$. Since every face of $G$ is a triangle, every face must contain a $12$ edge or a $34$ edge, as required. ...

14

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-75 (1991). ZBL0748.05056.

answered Apr 13 '18 at 15:30

13

Regarding Q1:
The graph is a subgraph of the visibility graph of the integer lattice. Every sublattice $x+2\mathbb{Z} \times 2\mathbb{Z}$ is an independent set in the visibility graph, and the integer lattice can be decomposed into four such sublattices (according to the parity of coordinates). This gives a proper $4$-coloring.

12

In practice, if you want to make sure that every instance is hard, then you should look to cryptography. For example, take two large primes, making sure to consult your cryptography textbook to avoid all the known pitfalls, and ask for a factorization of the product. Convert this to a graph-coloring problem using the usual reductions. If the graph doesn't ...

answered May 30 '14 at 16:04

Timothy Chow

58.8k1919 gold badges262262 silver badges444444 bronze badges

12

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 after converting the problem to SAT
and ran certified UNSAT solver.
The proof for unsatisfiability was only about 11MB.
The computation took few minutes and the ...

12

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 4-colouring $c$. We will use $\mathbb{Z}_2 \times \mathbb{Z}_2$ as the set of colours for $c$. Now for each edge $e \in E(G)$, colour $e$ with colour $c'(e):=...

11

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 the indegree of each vertex is $\leq 3$, and the indegree of each vertex on the boundary is $\leq 2$.
Proof: Let $G$ be a plane graph and let the boundary ...

11

Pach and Tóth proved that if $G$ is a $k$-planar graph (with $k \geq 1$), then
$|E(G)| \leq 4.108 \sqrt{k} |V(G)|$.
Thus, every $k$-planar graph has a vertex of degree at most $\lfloor8.216 \sqrt{k}\rfloor$. By induction, it follows that $k$-planar graphs can be coloured with $\lfloor8.216 \sqrt{k}\rfloor+1$ colours.
For $1 \leq k \leq 4$, they prove a ...

11

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

11

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

11

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). For the case of two colors they are characterized as the connected bipartite graphs, but for higher numbers of colors no such characterization is known.
In a ...

answered Jan 22 '19 at 0:05

Gjergji Zaimi

79.8k44 gold badges208208 silver badges372372 bronze badges

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

#### Related Tags

graph-colorings × 530graph-theory × 451

co.combinatorics × 283

hypergraph × 39

reference-request × 37

algorithms × 26

infinite-combinatorics × 25

set-theory × 23

computational-complexity × 23

extremal-graph-theory × 20

discrete-geometry × 19

ramsey-theory × 15

matching-theory × 14

perfect-matchings × 10

combinatorial-optimization × 9

chromatic-polynomial × 9

bipartite-graphs × 7

graph-minors × 7

cayley-graphs × 7

pr.probability × 6

lo.logic × 6

directed-graphs × 6

lattices × 5

nt.number-theory × 4

gr.group-theory × 4