TOPICS
Search

Harvey-Royle Graphs


HarveyRoyleGraphs

The Harvey-Royle graphs are the two graphs on 11 vertices illustrated above. The first has 22 edges and chromatic number 5, while the second has 19 edges and chromatic number 4. The first and second Harvey-Royle graphs have graph crossing number 3 and 1, respectively.

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