At most how many (proper) q-colorings does a regular graph admit? Galvin and Tetali conjectured that among all n-vertex, d-regular graphs with 2d|n, none admits more q-colorings than the disjoint union of n/2d copies of the complete bipartite graph Kd,d. In this note we give asymptotic evidence for this conjecture, showing that for each q ≥ 3 the number of proper q-colorings admitted by an n-vertex, d-regular graph is at most
(q2/4)n2qq/2n(1+o(1))2difqiseven((q2-1)/4)n2q+1(q+1)/2n(1+o(1))2difqisodd,\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\begin{array}{ll}(q^2/4)^\frac{n}{2}\binom{q}{q/2}^\frac{n(1+o(1))}{2d} &{\rm if}\; q \; {\rm is}\; {\rm even}\\((q^2-1)/4)^\frac{n}{2}\binom{q+1}{(q+1)/2}^\frac{n(1+o(1))}{2d} & {\rm if}\; q\; {\rm is}\; {\rm odd,}\end{array}$$\end{document}where o(1)→0\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$${o(1)\rightarrow 0}$$\end{document} as d→∞\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$${d \rightarrow \infty}$$\end{document} ; these bounds agree up to the o(1) terms with the counts of q-colorings of n/2d copies of Kd,d. Along the way we obtain an upper bound on the number of colorings of a regular graph in terms of its independence number. For example, we show that for all even q ≥ 4 and fixed ɛ > 0 there is δ=δ(ε,q)\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$${\delta=\delta(\varepsilon,q)}$$\end{document} such that the number of proper q-colorings admitted by an n-vertex, d-regular graph with no independent set of size n(1-ε)/2\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$${n(1-\varepsilon)/2}$$\end{document} is at most
(q2/4-δ)n2,\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$(q^2/4-\delta)^\frac{n}{2},$$\end{document}with an analogous result for odd q.
