Maximizing $H$-colorings of connected graphs with fixed minimum degree

Abstract

For graphs $G$ and $H$, an $H$-coloring of $G$ is a map from the vertices of $G$ to the vertices of $H$ that preserves edge adjacency. We consider the following extremal enumerative question: for a given $H$, which connected $n$-vertex graph with minimum degree $\delta$ maximizes the number of $H$-colorings? We show that for non-regular $H$ and sufficiently large $n$, the complete bipartite graph $K_{\delta ,n-\delta }$ is the unique maximizer. As a corollary, for non-regular $H$ and sufficiently large $n$ the graph $K_{k,n-k}$ is the unique $k$-connected graph that maximizes the number of $H$-colorings among all $k$-connected graphs. Finally, we show that this conclusion does not hold for all regular $H$ by exhibiting a connected $n$-vertex graph with minimum degree $\delta$ which has more $K_q$-colorings (for sufficiently large $q$ and $n$) than $K_{\delta ,n-\delta }$.

10 pages, to appear in Journal of Graph Theory

References in corpus (1)

• The Bipartite Swapping Trick on Graph Homomorphisms