On the maximum number of colorings of a graph

Abstract

Let ${\mathcal{C}}_k(n)$ be the family of all connected $k$-chromatic graphs of order $n$. Given a natural number $x\ge k$, we consider the problem of finding the maximum number of $x$-colorings among graphs in ${\mathcal{C}}_k(n)$. When $k\le 3$ the answer to this problem is known, and when $k\ge 4$ the problem is wide open. For $k\ge 4$ it was conjectured that the maximum number of $x$-colorings is $x(x-1)\cdots (x-k+1)x^{n-k}$. In this article, we prove this conjecture under the additional condition that the independence number of the graphs is at most $2$.

arXiv commentto appear in Journal of Combinatorics