Extremal H-colorings of graphs with fixed minimum degree

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 $\mathrm{hom}(G,H)$ for the number of $H$-colorings of $G$, we show that for fixed $H$ and $\delta =1$ or $\delta =2$, $$\mathrm{hom}(G,H)\le \max \{\mathrm{hom}(K_{\delta +1},H{)}^{\frac{n}{\delta +1}},\mathrm{hom}(K_{\delta ,\delta },H{)}^{\frac{n}{2\delta }},\mathrm{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 $\mathrm{hom}(K_{\delta +1},H{)}^{\frac{n}{\delta +1}}$ and other $H$ for which the maximum is achieved by $\mathrm{hom}(K_{\delta ,\delta },H{)}^{\frac{n}{2\delta }}$. For $\delta \geq 3$(andsufficientlylarge$n$),weprovideainfinitefamilyof$H$ for which $\mathrm{hom}(G,H)\le \mathrm{hom}(K_{\delta ,n-\delta },H)$ for any $n$-vertex $G$ with minimum degree $\delta$. The results generalize to weighted $H$-colorings.