Maximizing the Number of H-Colorings of Graphs with a Fixed Minimum Degree.

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 hom (G , H) . Given a fixed graph H and family of graphs G , what is the maximum value of hom (G , H) over all G ∈ G ? For any n-vertex d-regular graph G, it has been conjectured that hom (G , H) ≤ max G ∗ hom (G ∗ , H) n | V (G ∗) | , <graphic href="373_2024_2854_Article_Equ11.gif"></graphic> where the maximum is taken over all d-regular graphs G ∗ with at most κ (d) vertices, where κ (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 δ . For fixed δ and H, we show that hom (G , H) ≤ max G ∗ hom (G ∗ , H) n | V (G ∗) | <graphic href="373_2024_2854_Article_Equ12.gif"></graphic> where the maximum is taken over all graphs G ∗ with minimum degree δ on at most κ (δ , H) vertices, where κ (δ , H) is a constant that depends on δ and H, and the graph G ∗ = K δ , n - δ . For fixed δ , we also find new conditions on H for which hom (G , H) ≤ hom (K δ , n - δ , H) for all n-vertex graphs G with minimum degree at least δ when n is sufficiently large. [ABSTRACT FROM AUTHOR]