Extremal H-colorings of trees and 2-connected graphs

First, we find a class of graphs H with the property that for each H∈H, the n-vertex tree that minimizes the number of H-colorings is the path Pn. We then present a new proof of a theorem of Sidorenko, valid for large n, that for every H the star K1,n−1 is the n-vertex tree that maximizes the number of H-colorings. Our proof uses a stability technique which we also use to show that for any non-regular H (and certain regular H) the complete bipartite graph K2,n−2 maximizes the number of H-colorings of n-vertex 2-connected graphs. Finally, we show that the cycle Cn has the most proper q-colorings among all n-vertex 2-connected graphs.