Beraha's Conjecture and Cyclic Graphs

cyclic graph of order

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∞

.