TOPICS
Search

O'Donnell Graphs

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
ODonnellGraphs

The term "O'Donnell graphs" is used in this work for a set of graphs on 40, 46, and 56 vertices, together with a 15-vertex graph 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 moth graph among the Chilakamarri graphs) were the (reverse) incrementally smallest known such graph. They were subsequently supplanted by the Hochberg-O'Donnell fish graph and finally in the (presumed to be smallest possible) 17-vertex graph in the Exoo-Ismailescu graphs.

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.

Referenced on Wolfram|Alpha

O'Donnell Graphs

Cite this as:

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

Subject classifications