Extremal H-colorings of graphs with fixed minimum degree

John Engbers

Published 2013-07-23, updated 2016-10-20Version 2

For graphs $G$ and $H$, a homomorphism from $G$ to $H$, or $H$-coloring of $G$, is a map from the vertices of $G$ to the vertices of $H$ that preserves adjacency. When $H$ is composed of an edge with one looped endvertex, an $H$-coloring of $G$ corresponds to an independent set in $G$. Galvin showed that, for sufficiently large $n$, the complete bipartite graph $K_{\delta,n-\delta}$ is the $n$-vertex graph with minimum degree $\delta$ that has the largest number of independent sets. In this paper, we begin the project of generalizing this result to arbitrary $H$. Writing $\hom(G,H)$ for the number of $H$-colorings of $G$, we show that for fixed $H$ and $\delta = 1$ or $\delta = 2$, \[ \hom(G,H) \leq \max \{\hom(K_{\delta+1},H)^{\frac{n}{\delta+1}}, \hom(K_{\delta,\delta},H)^{\frac{n}{2\delta}}, \hom(K_{\delta,n-\delta},H)\} \] for any $n$-vertex $G$ with minimum degree $\delta$ (for sufficiently large $n$). We also provide examples of $H$ for which the maximum is achieved by $\hom(K_{\delta+1},H)^{\frac{n}{\delta+1}}$ and other $H$ for which the maximum is achieved by $\hom(K_{\delta,\delta},H)^{\frac{n}{2\delta}}$. For $\delta \geq 3$ (and sufficiently large $n$), we provide a infinite family of $H$ for which $\hom(G,H) \leq \hom(K_{\delta,n-\delta},H)$ for any $n$-vertex $G$ with minimum degree $\delta$. The results generalize to weighted $H$-colorings.