On the maximum number of colorings of a graph

Let $C_k (n)$ be the family of all connected $k$-chromatic graphs of order $n$. Given a natural number $x \geq k$, we consider the problem of finding the maximum number of $x$-colorings among graphs in $C_k (n)$. When $k \leq 3$ the answer to this problem is known, and when $k \geq 4$ the problem is wide open. For $k \geq 4$ it was conjectured that the maximum number of $x$-colorings is $x(x-1) \dotsm (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$.

Keywords

$x$-coloring, chromatic number, $k$-chromatic, chromatic polynomial

2010 Mathematics Subject Classification

05C15, 05C30, 05C31, 05C35

Full Text (PDF format)

Received 4 July 2016

Published 18 May 2018