TOPICS
Search

Exoo-Ismailescu Graphs

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A number of graphs are associated with Geoffrey Exoo and Dan Ismailescu.

ExooIsmailescuGraphs17

The graphs on 17, 19, and 21 vertices (Exoo and Ismailescu 2016, Soifer 2024) are examples of small triangle-free unit-distance graphs with chromatic number 4 and girth 4. These improve on larger examples previously found by O'Donnell, Chilakamarri, and Hochberg between 1994 and 1996, as summarized by Soifer (2008, Table 15.1, p. 445) and Soifer (2024, Table 15.1, p. 145) and reproduced below. Moreover, there is evidence that no smaller such graph exist (Soifer 2024). The 17-vertex Exoo-Ismailescu graph decorates the front cover of the October 2016 issue of Geombinatorics.

vertex countgraphreference
6448Wormald graphWormald (1979)
5656-O'Donnell graphO'Donnell (1994)
47Chilakamarri moth graphChilakamarri (1995)
4646-O'Donnell graphunpublished (1995)
4050-O'Donnell graphO'Donnell (1995)
23Hochberg-O'Donnell fish graphHochberg and O'Donnell (1995)
2121-Exoo-Ismailescu graphExoo and Ismailescu (2016)
21Kiteck-Payne graphKiteck and Payne (2021)
1919-Exoo-Ismailescu graphExoo and Ismailescu (2016)
1717-Exoo-Ismailescu graphExoo and Ismailescu (2016)
ExooIsmailescuGraphs40

Graphs on 40, 49, 51, 79, and 627 vertices are unit-distance graphs with girth 3 that appear in Exoo and Ismailescu (2018).

ExooIsmailescuGraphs205

Graphs on 205 and 214 vertices appear in Exoo and Ismailescu (2019) as graphs labeled G and H, respectively.

Exoo-Ismailescu graphs are implemented in the Wolfram Language as GraphData["ExooIsmailescuGraph17"] etc.

See also

Unit-Distance Graph

Explore with Wolfram|Alpha

References

Chilakamarri, K. "A 4-Chromatic Unit Distance Graph With No Triangles." Geomcombinatorics 4, No. 3, 64-76, 1995.Exoo, G. and Ismailescu, D. "Small Order Triangle-Free 4-Chromatic Unit Distance Graphs." Geombinatorics 26, No. 2, 49-64, 2016.Exoo, G. and Ismailescu, D. "The Chromatic Number of the Plane Is at Least 5--A New Proof." 1 May 2018. https://arxiv.org/abs/1805.00157.Exoo, G. and Ismailescu, D. "A 6-Chromatic Two-Distance Graph in the Plane." 29 Sep 2019. https://arxiv.org/abs/1909.13177.Hochberg, R. and O'Donnell, P. "Some 4-Chromatic Unit-Distance Graphs Without Small Cycles." Geombinatorics 5, 137-141, 1996.Kiteck, D. and Payne, K. "A 21-Vertex 4-Chromatic Unit-Distance Graph of Girth 4." Ball State Undergraduate Mathematics Exchange 15, No. 1, 2-9, 2021.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.Wormald, N. C. "A 4-Chromatic Graph With a Special Plane Drawing." J. Austral. Math. Soc. 28, 1-8, 1979.

Cite this as:

Weisstein, Eric W. "Exoo-Ismailescu Graphs." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Exoo-IsmailescuGraphs.html

Subject classifications