44 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 (...
David's user avatar
  • 575
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 ...
Fedor Petrov's user avatar
34 votes
Accepted

Can we three-color a tiling of the plane with Smith, Meyers, Kaplan, and Goodman-Strauss's einstein?

No, you cannot three-color that tiling. Here's a finite part of the tiling from page 10 top left of the article, the tile numbered 2 here is the one darkened on that figure. This part cannot be three-...
Zsbán Ambrus's user avatar
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 ...
Gjergji Zaimi's user avatar
25 votes

Non-definability of graph 3-colorability in first-order logic

Here is one way to do it. 2-colorability case. First let's warm up with the 2-colorability case. Notice that odd-length cycles are not 2-colorable, since the colors have to alternate as you go around ...
Joel David Hamkins's user avatar
21 votes
Accepted

Parity and the Axiom of Choice

The Parity Principle follows from the axiom $\mathbf C_2$ (defined below) which is weaker than the Axiom of Choice. I don't know whether the Parity Principle implies $\mathbf C_2$, but that's another ...
bof's user avatar
  • 11.1k
17 votes
Accepted

Can the positive integers be colored so that elements of same color never add to a square?

No. See the paper below, which handles more polynomials than just perfect squares. On the number of monochromatic solutions of $x+y = z^2$. Ayman Khalfalah and Endre Szemerédi. Combinatorics, ...
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 ...
Peter Heinig's user avatar
  • 5,951
15 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 $...
Tony Huynh's user avatar
  • 31.3k
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.
Gordon Royle's user avatar
  • 12.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. ...
Incompactness's user avatar
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-...
Asaf Karagila's user avatar
  • 37.8k
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}...
Timothy Chow's user avatar
  • 77.8k
13 votes

How can one construct a four-coloring of a tiling of the plane with Smith, Myers, Kaplan, and Goodman-Strauss's aperiodic monotile?

I tried to find a colouring where one of the colours comprised exactly the 'flipped' tiles. So I coloured all of the flipped tiles blue and then found three of the remaining tiles which were all ...
Oscar Cunningham's user avatar
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 ...
joro's user avatar
  • 24.2k
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

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 ...
Tony Huynh's user avatar
  • 31.3k
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). ...
Gjergji Zaimi's user avatar
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\...
Alessandro Codenotti's user avatar
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....
Gordon Royle's user avatar
  • 12.3k
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 ...
Gro-Tsen's user avatar
  • 29.6k
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^{\...
Tony Huynh's user avatar
  • 31.3k
10 votes

Minimum modifications to make a graph bipartite

You want to partition the vertices into two parts and minimizing the number of edges between vertices in the same part. In other words you want to maximize the number of edges between the two parts. ...
John Machacek's user avatar
10 votes
Accepted

Do planar graphs have an acyclic two-coloring?

G. Chartrand, H.V. Kronk, C.E. Wall showed in "The point-arboricity of a graph" (Israel J. Math., 6 (1968), pp. 169–175) that the vertex-set of any planar graph can be partitioned into three induced ...
monkeymaths's user avatar
  • 1,159
10 votes
Accepted

Chromatic number of a connected Hausdorff space

The answer is no. A space is called resolvable if it contains two disjoint dense subspaces. Clearly $X$ is resolvable if and only if $\chi(X)=2$. Lets prove by induction on $n \geq 2$ that if $\chi(X)...
Ramiro de la Vega's user avatar
10 votes

Doubly periodic 4 color theorem?

As Michael Klug points out in the comments, I've thought about related questions before. I'll make a few comments on the question. Firstly, the usual reduction allows one to consider triangulations ...
Ian Agol's user avatar
  • 66.5k
9 votes
Accepted

How many colors do we need to avoid bichromatic triangles?

Problems of this variety have been studied, beginning with a paper of Erdős and Gyárfás, 'A variant of the classical Ramsey problem'. In that paper, they define a function $f(n,p,q)$ to be the ...
David Conlon's user avatar
9 votes

Maximum number of perfect matchings in a planar graph?

In order to get an upper bound on $\alpha_4$ (which is probably far from being a tight bound), you can use the Kahn-Lovász Theorem (a generalisation of Brègman's Theorem). The Kahn-Lovász Theorem says ...
Jon Noel's user avatar
  • 761
9 votes
Accepted

Increasing the chromatic number by "folding" two vertices of distance 2

The answer is no. We may assume $G$ is not complete. If $G$ is a cycle, then identifying any two vertices at distance 2 does not change the chromatic number. Now assume that $G$ is not a cycle. ...
David Wood's user avatar
  • 1,232
9 votes
Accepted

Equitable edge coloring of graphs

Yes. Choose any proper edge coloring with $\Delta+1$ colors (it exists by Vizing theorem). If we have two color classes with $a$ and $b$ edges respectively, $a\geqslant b+2$ (say, $a$ red eges and $b$ ...
Fedor Petrov's user avatar

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