Journal of Combinatorics

Volume 9 (2018)

Number 3

On the maximum number of colorings of a graph

Pages: 489 – 497

DOI: http://dx.doi.org/10.4310/JOC.2018.v9.n3.a4

Author

Aysel Erey (Department of Mathematics, University of Denver, Colorado, U.S.A.)

Abstract

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