Graph Coloring · Challenge problem

The $n$-cycle's chromatic polynomial is $P(C_n,k) = (k-1)^n + (-1)^n(k-1)$. Using $k=3$ colors, what is the smallest $n$ for which $P(C_n,3)$ exceeds one million?