Maximizing the number of $x$-colorings of $4$-chromatic graphs

Abstract

Let ${\mathcal{C}}_4(n)$ be the family of all connected $4$-chromatic graphs of order $n$. Given an integer $x\ge 4$, we consider the problem of finding the maximum number of $x$-colorings of a graph in ${\mathcal{C}}_4(n)$. It was conjectured that the maximum number of $x$-colorings is equal to $(x{)}_{\downarrow 4}(x-1{)}^{n-4}$ and the extremal graphs are those which have clique number $4$ and size $n+2$. In this article, we reduce this problem to a \textit{finite} family of graphs. We show that there exist a finite family $\mathcal{F}$ of connected $4$-chromatic graphs such that if the number of $x$-colorings of every graph $G$ in $\mathcal{F}$ is less than $(x{)}_{\downarrow 4}(x-1{)}^{|V(G)|-4}$ then the conjecture holds to be true.

19 pages, 5 figures

Cited by in corpus (1)

• Tomescu's graph coloring conjecture for $\ell$-connected graphs