Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. P. O'Donnell, A triangle-free 4-chromatic graph in the plane, Geombinatorics 4 (1994), no. 1, 23–29, constructs a unit distance graph in the plane on 5656 vertices with girth 44 and chromatic number 44, as the site's commentary on Problem 705 reports. If its point set has no unit distance besides the graph's edges, no k≤4k\le4 makes every finite unit distance graph of girth at least kk 33-colorable.

Covers. No k≤4k\le4 works. Nothing is settled for k≥5k\ge5; Wormald's graph of girth 55 settles k=5k=5 (Wormald 1979), and O'Donnell's dissertation every kk (O'Donnell 1999).

Depends on. No page of this wiki.

Standing. Claimed. The paper appeared in Geombinatorics, whose archive lists it in the issue of July 1994 and holds no copy online. The problem asks about the faithful graph of a point set, with an edge exactly when two points are at distance 11, while O'Donnell's own definition of a unit distance graph in his 1999 dissertation allows further unit distances between non-adjacent vertices. Whether this paper's point set has none is not established from the paper, so refereed is not listed. The curator's label credits the dissertation, not this paper.

Dating. The journal's archive dates the issue July 1994; the day is a placeholder.