TOPICS
Search

Chilakamarri Graphs

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
ChilakamarriGraphs

The Chilakamarri graphs are a set of graphs on 12, 24, and 47 vertices used in the construction of the 47-vertex unit-distance graph with chromatic number 4 and girth 4. For a time, this was the smallest known such graph, but has subsequently been supplanted by smaller graphs, culminating in the presumed to be smallest possible 17-vertex Exoo-Ismailescu graph.

See also

Exoo-Ismailescu Graphs, O'Donnell Graphs

Explore with Wolfram|Alpha

References

Chilakamarri, K. "A 4-Chromatic Unit Distance Graph With No Triangles." Geomcombinatorics 4, No. 3, 64-76, 1995.Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, 2008.Soifer, A. The New Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, 2nd ed. New York: Springer, 2024.

Cite this as:

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

Subject classifications