#### Document Type

Article

#### Language

English

#### Publication Date

1-2017

#### Publisher

Elsevier

#### Source Publication

Journal of Combinatoral Theory, Series B

#### Source ISSN

0095-8956

#### Abstract

For graphs *G* and *H*, an *H-coloring* of *G* is an adjacency preserving map from the vertices of *G* to the vertices of *H*. *H*-colorings generalize such notions as independent sets and proper colorings in graphs. There has been much recent research on the extremal question of finding the graph(s) among a fixed family that maximize or minimize the number of *H*-colorings. In this paper, we prove several results in this area.

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 P_{n}. We then present a new proof of a theorem of Sidorenko, valid for large *n*, that for *every H * the star K_{1,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 K_{2,n−2} maximizes the number of *H*-colorings of *n *-vertex 2-connected graphs. Finally, we show that the cycle C_{n} has the most proper *q*-colorings among all *n*-vertex 2-connected graphs.

## Comments

Accepted version. Journal of Combinatorial Theory, Series B,Vol. 122 (January, 2017): 800-814. DOI. © 2017 Elsevier B.V. Used with permission.