Extremal H-colorings of graphs with fixed minimum degree

Original · EN

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δ,ₙ₋δ is the n-vertex graph with minimum degree δ that has the largest number of independent sets. In this paper, we begin the project of generalizing this result to arbitrary H. Writing (G,H) for the number of H-colorings of G, we show that for fixed H and δ= 1 or δ= 2, (G,H) ≤ {(Kδ₊₁,H)ⁿ/δ⁺¹, (Kδ,δ,H)ⁿ/²δ, (Kδ,ₙ₋δ,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 (Kδ₊₁,H)ⁿ/δ⁺¹ and other H for which the maximum is achieved by (Kδ,δ,H)ⁿ/²δ. For δ≥ 3 (and sufficiently large n), we provide a infinite family of H for which (G,H) ≤ (Kδ,ₙ₋δ,H) for any n-vertex G with minimum degree δ. The results generalize to weighted H-colorings.