Beraha's Conjecture, Wheels, and Cyclic Graphs
Beraha's Conjecture, Wheels, and Cyclic Graphs
A graph coloring assigns colors to the vertices of a graph in such a way that a pair of vertices joined by an edge do not get the same color. The chromatic polynomial of a graph gives the number of ways of coloring the graph with colors.
x
Beraha's numbers are . Tutte conjectured that there is a link between Beraha's numbers and some classes of graphs.
B(n)=4
2
cos
π
n
This Demonstration shows that for a small number of vertices, it is not obvious what the connection is between the roots of the chromatic polynomial of a cyclic graph (green), the roots of the chromatic polynomial of the corresponding wheel graph (purple), and Beraha's numbers (red).
However, taking more vertices clearly shows a relationship between these three sets of numbers.