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 (...
- 575
40
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 ...
- 103k
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-...
- 1,924
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 ...
- 85.1k
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 ...
- 225k
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 ...
- 11.9k
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, ...
17
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 ...
- 3,077
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 ...
- 6,001
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 $...
- 31.5k
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.
- 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. ...
- 166
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-...
- 38.2k
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}...
- 78.7k
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 ...
- 31.5k
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). ...
- 85.1k
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,904
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....
- 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 ...
- 30.2k
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^{\...
- 31.5k
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. ...
- 7,775
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 ...
- 1,169
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)...
- 11.5k
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 ...
- 66.8k
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 ...
- 806
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 ...
- 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.
...
- 1,253
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$ ...
- 103k
9
votes
Accepted
When does a graph have a circular orientation? Or equivalently can anyone help me characterize this particular class of $3$-colorable perfect graphs?
The class is exactly the class of bipartite graphs ∪ complete 3-partite graphs.
Such a graph must be paw-free. To check this, note that the orientation of the triangle in the paw must be cyclic, and ...
- 9,421
Only top scored, non community-wiki answers of a minimum length are eligible