TOPICS
Search

O'Donnell Graphs

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
ODonnellGraphs

The O'Donnell graphs are a set of graphs on 40, 46, and 56 vertices (together with a graph on 15 vertices used to construct the 40-vertex graph) that are unit-distance with chromatic number 4 and girth 4. For a time, these (together with the Chilakamarri moth graph) were the (reverse) incrementally smallest known such graph. They were subsequently been supplanted by the Hochberg-O'Donnell fish graph and finally in the (presumed to be smallest possible) 17-vertex Exoo-Ismailescu graph.

The 40-O'Donnell graph is a C_5 cyclic group graph.

See also

Chilakamarri Graphs, Exoo-Ismailescu Graphs, Hochberg-O'Donnell Fish Graph, Unit-Distance Graph

Explore with Wolfram|Alpha

References

O'Donnell, P. "A Triangle-Free 4-Chramatic Graph in the Plane." Geombinatorics 4, No. 1, 23-29, 1994.O'Donnell, P. "A 40 Vertex 4-Chromatic Triangle-Free Unit Distance Graph." Geombinatorics 5, No. 1, 30-34, 1995.Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, 2008.Soifer, A. "Exoo-Ismailescu: The Final Word on Problem 15.4." Ch. 16 in The New Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, 2nd ed. New York: Springer, pp. 147-160, 2024.

Cite this as:

Weisstein, Eric W. "O'Donnell Graphs." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ODonnellGraphs.html

Subject classifications