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 δ , n − δis the n ‐vertex graph with minimum degree δ that has the largest number of independent sets. In this article, 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 δ = 1 or δ = 2 , hom ( G , H ) ≤ max { hom ( K δ + 1 , H ) n δ + 1, hom ( K δ , δ , H ) n 2 δ, hom ( K δ , n − δ , H ) } for any n ‐vertex G with minimum degree δ (for sufficiently large n ). We also provide examples of H for which the maximum is achieved by hom ( K δ + 1 , H ) n δ + 1and other H for which the maximum is achieved by hom ( K δ , δ , H ) n 2 δ. For δ ≥ 3 (and sufficiently large n ), we provide an infinite family of H for which hom ( G , H ) ≤ hom ( K δ , n − δ , H )for any n ‐vertex G with minimum degree δ. The results generalize to weighted H ‐colorings.