Wiki
Wiki

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

Updated


Claim. K. B. Chilakamarri, A 4-chromatic unit-distance graph with no triangles, Geombinatorics 4 (1995), no. 3, 64–76, constructs an infinite family of unit distance graphs in the plane with girth 44 and chromatic number 44, the smallest on 4747 vertices, as the site's commentary on Problem 705 reports. If its point sets have no unit distance besides the graphs' 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 January 1995 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, and whether this paper's point sets carry no unit distance besides the graphs' edges is not established from the paper, so refereed is not listed. The curator's label credits O'Donnell's dissertation, not this paper.

Dating. The journal's archive dates the issue January 1995; the day is a placeholder.