Contents Online

# Journal of Combinatorics

## Volume 9 (2018)

### Number 3

### On the maximum number of colorings of a graph

Pages: 489 – 497

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

#### Author

#### 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

Received 4 July 2016

Published 18 May 2018