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 vertices with girth and chromatic number , as the site's commentary on Problem 705 reports. If its point set has no unit distance besides the graph's edges, no makes every finite unit distance graph of girth at least -colorable.
Covers. No works. Nothing is settled for ; Wormald's graph of girth settles (Wormald 1979), and O'Donnell's dissertation every (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 , 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.