Maximum number of colorings of (2 k, k 2 )‐graphs

Abstract Let ${\cal F}_{{2}{k},{k}^{2}}$ consist of all simple graphs on 2 k vertices and ${k}^{2}$ edges. For a simple graph G and a positive integer $\lambda$ , let ${P}_{G}(\lambda)$ denote the number of proper vertex colorings of G in at most $\lambda$ colors, and let $f(2k, k^{2}, \lambda) = {\rm max} \{{P}_{G}(\lambda):{G} \in {\cal F}_{{2}{k},{k}^{2}}\}$ . We prove that $f(2{k}, {k}^{2}, 3) = {P}_{{K}_{{k}, {k}}}(3)$ and ${K}_{{k},{k}}$ is the only extremal graph. We also prove that $f({2}{k}, {k}^{2}, 4) = ({6}+{o}(1)){4}^{k}$ as ${k}\to \infty$ . © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 135–148, 2007