WOLFRAM|DEMONSTRATIONS PROJECT

Beraha's Conjecture and Cyclic Graphs

​
cyclic graph of order
B(1)
2cos
2π
1
+2
4
4.
B(2)
2cos
2π
2
+2
0
0.
B(3)
2cos
2π
3
+2
1
1.
B(4)
2cos
2π
4
+2
2
2.
B(5)
2cos
2π
5
+2
2+
1
2
(
5
-1)
2.61803
B(6)
2cos
2π
6
+2
3
3.
B(7)
2cos
2π
7
+2
2+2sin
3π
14
3.24698
B(8)
2cos
2π
8
+2
2+
2
3.41421
The chromatic polynomial of a graph gives the number of ways to color the graph with
x
colors, such that no pair of connected vertices shares the same color.
Beraha's conjecture (due to Tutte) says that for each
n
, the Beraha number
B
n
=2+2cos
2π
n
is the limit of roots of at least one family of chromatic polynomials.
This Demonstration shows that:
1) All cyclic graphs of odd order have a root of their chromatic polynomial equal to
B(4)
.
2) For even order
n
, let
P
n
be the root with largest real part and positive imaginary part, and let
N
n
be the complex conjugate root (the chromatic polynomial has real coefficients so complex roots come in conjugate pairs). Then the sequences
P
n
and
N
n
converge to
B(4)
as
n∞
.