For graphs G and H, an H-coloring of G is an adjacency-preserving map from the vertex set of G to the vertex set of H. The number of H-colorings of G is denoted \(\text {hom}(G,H)\) . Given a fixed graph H and family of graphs \(\mathcal {G}\) , what is the maximum value of \(\text {hom}(G,H)\) over all \(G \in \mathcal {G}\) ? For any n-vertex d-regular graph G, it has been conjectured that \(\begin{aligned} \text {hom}(G,H) \le \max _{G^*} \text {hom}(G^*,H)^{\frac{n}{|V(G^*)|}}, \end{aligned}\) where the maximum is taken over all d-regular graphs \(G^*\) with at most \(\kappa (d)\) vertices, where \(\kappa (d)\) is a constant that depends on d. This has been verified for various classes of H, but remains open in general. We consider the related family of n-vertex graphs G with minimum degree at least \(\delta \) . For fixed \(\delta \) and H, we show that \(\begin{aligned} \text {hom}(G,H) \le \max _{G^*} \text {hom}(G^*,H)^{\frac{n}{|V(G^*)|}} \end{aligned}\) where the maximum is taken over all graphs \(G^*\) with minimum degree \(\delta \) on at most \(\kappa (\delta ,H)\) vertices, where \(\kappa (\delta ,H)\) is a constant that depends on \(\delta \) and H, and the graph \(G^*=K_{\delta ,n-\delta }\) . For fixed \(\delta \) , we also find new conditions on H for which \(\text {hom}(G,H) \le \text {hom}(K_{\delta ,n-\delta },H)\) for all n-vertex graphs G with minimum degree at least \(\delta \) when n is sufficiently large.
