Wiki
Wiki

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

Updated

Claims

../

1979_08_01_wormald: Wormald (1979) gives a finite point set in the plane whose unit distance graph has girth 5 and chromatic number 4, so no girth bound k at most 5 forces 3-colorability; refereed.

1994_07_01_odonnell: O'Donnell (1994) gives a 4-chromatic unit distance graph of girth 4 on 56 vertices in the plane, so no girth bound k at most 4 forces 3-colorability.

1995_01_01_chilakamarri: Chilakamarri (1995) gives an infinite family of 4-chromatic unit distance graphs of girth 4, the smallest on 47 vertices, so no girth bound k at most 4 forces 3-colorability.

1999_10_01_odonnell: O'Donnell's 1999 dissertation constructs, for every k at least 3, a finite unit distance graph in the plane with girth k and chromatic number 4, so no girth bound forces 3-colorability; credited by the site's curator in 2026.