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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#### Related Tags

graph-colorings × 616graph-theory × 518

co.combinatorics × 331

hypergraph × 54

reference-request × 40

infinite-combinatorics × 38

algorithms × 31

set-theory × 30

computational-complexity × 23

extremal-graph-theory × 23

discrete-geometry × 22

ramsey-theory × 18

matching-theory × 13

combinatorial-optimization × 12

cayley-graphs × 11

bipartite-graphs × 10

graph-minors × 10

perfect-matchings × 9

chromatic-polynomial × 9

lo.logic × 8

pr.probability × 7

directed-graphs × 7

planar-graphs × 7

extremal-combinatorics × 6

colorings × 6