TOPICS
Search

Harvey-Royle Graphs

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
HarveyRoyleGraphs

The Harvey-Royle graphs are the two 11-vertex graphs illustrated above. The first has 22 edges and chromatic number 5, while the second has 19 edges and chromatic number 4.

Their chromatic polynomials have B_(10)=phi+2 as a chromatic root, where B_(10) is a Beraha constant and phi is the golden ratio. They supplied the first examples of graphs having B_(10) as a chromatic root. Since every other noninteger Beraha constant had already been ruled out as a chromatic root, the examples resolved a question of Salas and Sokal (2001) and completed the determination of which Beraha constants can be chromatic roots (Harvey and Royle 2020).

The Harvey-Royle graphs are implemented in the Wolfram Language as GraphData["HarveyRoyleGraph1"] and GraphData["HarveyRoyleGraph2"].

See also

Chromatic Polynomial, Chromatic Root, Royle Graphs

Explore with Wolfram|Alpha

References

Harvey, D. J. and Royle, G. F. "Chromatic Roots at 2 and the Beraha Number B_(10)." J. Graph Theory 95, 445-456, 2020. https://doi.org/10.1002/jgt.22566.Salas, J. and Sokal, A. D. "Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. I. General Theory and Square-Lattice Chromatic Polynomial." J. Stat. Phys. 104, 609-699, 2001. https://doi.org/10.1023/A:1010376605067.

Cite this as:

Weisstein, Eric W. "Harvey-Royle Graphs." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Harvey-RoyleGraphs.html

Subject classifications