TOPICS
Search

Hochberg-O'Donnell Star Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
HochbergODonnellStarGraph

The Hochberg-O'Donnell star graph is the 45-vertex, 85-edge graph illustrated above. It has graph diameter 4.

It is a unit-distance graph with girth 5 and chromatic number 4. When it was published, it reduced the smallest known number of vertices for such a graph from 6448 to 45. The minimum possible number of vertices for a 4-chromatic unit-distance graph of girth 5 remains unknown (Hochberg and O'Donnell 1996; Soifer 2024, pp. 143-145).

The Hochberg-O'Donnell star graph is implemented in the Wolfram Language as GraphData["HochbergODonnellStarGraph"].

See also

Hochberg-O'Donnell Fish Graph, Unit-Distance Graph

Explore with Wolfram|Alpha

References

Hochberg, R. and O'Donnell, P. "Some 4-Chromatic Unit-Distance Graphs Without Small Cycles." Geombinatorics 5, 137-141, 1996.House of Graphs. "Hochberg-O'Donnell Star Graph." https://houseofgraphs.org/graphs/51405.Soifer, A. "A 45-Vertex, Girth 5, 4-Chromatic Unit Distance Graph." §15.5 in The New Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, 2nd ed. New York: Springer, pp. 143-145, 2024.

Cite this as:

Weisstein, Eric W. "Hochberg-O'Donnell Star Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Hochberg-ODonnellStarGraph.html

Subject classifications