Problem 705

Let $G$ be a finite unit distance graph in $\mathbb{R}^2$ (i.e. the vertices are a finite collection of points in $\mathbb{R}^2$ and there is an edge between two points if and only if the distance between them is $1$ ).

Is there some $k$ such that if $G$ has girth $\geq k$ (i.e. $G$ contains no cycles of length $<k$ ) then $\chi(G)\leq 3$ ?

Source: erdosproblems.com/705

Graph theory
Chromatic number

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. The site credits O'Donnell's 1999 dissertation, which gives a finite unit distance graph of girth $k$ and chromatic number $4$ for every $k\ge3$ ; the accepted claim is his Theorem 28. O'Donnell's unit distance graphs allow unit distances between non-adjacent vertices, and the claim page records how the problem's faithful graph is reached.

Ch95: Chilakamarri, Kiran B., A $4$ -chromatic unit-distance graph with no triangles. Geombinatorics 4 (1995), no. 3, 64-76.
OD94: O'Donnell, Paul, A triangle-free $4$ -chromatic graph in the plane. Geombinatorics 4 (1994), no. 1, 23-29.
OD99: P. O'Donnell, High girth unit-distance graphs. PhD Dissertation, Rutgers University (1999); title page dated October 1999.
OD00: O'Donnell, Paul, Arbitrary girth, $4$ -chromatic unit distance graphs in the plane. Part I: Graph description. Geombinatorics 9 (2000), no. 3, 145-150; Part II: Graph embedding. Geombinatorics 9 (2000), no. 4, 180-193.
Wo79: Wormald, Nicholas, A $4$ -chromatic graph with a special plane drawing. J. Austral. Math. Soc. Ser. A 28 (1979), no. 1, 1-8.
dG18: de Grey, Aubrey D. N. J., The chromatic number of the plane is at least 5. Geombinatorics 28 (2018), no. 1, 18-31.

Problem 705

Status

Proof claims

Discussion