Visitar URL original
Hochberg-O'Donnell Star Graph -- from Wolfram MathWorld
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).

Shukla (2026) subsequently lowered the upper bound to 43 vertices for 4-chromatic unit-distance graphs of girth 5 by constructing the 43-vertex member of the Shukla graphs.

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.Shukla, C. "A 43-Vertex 4-Chromatic Unit-Distance Graph in the Plane with Girth 5." 7 Nov 2026. https://arxiv.org/abs/2611.10735v1.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