## Document Type

Article

## Language

English

## Publication Date

1-2017

## Publisher

Elsevier

## Source Publication

Journal of Combinatorial 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.

## Recommended Citation

Engbers, John and Galvin, David, "Extremal *H*-Colorings of Trees and 2-connected Graphs" (2017). *Mathematics, Statistics and Computer Science Faculty Research and Publications*. 488.

https://epublications.marquette.edu/mscs_fac/488

## Comments

Accepted version

. Journal of Combinatorial Theory, Series B,Vol. 122 (January, 2017): 800-814. DOI. © 2017 Elsevier B.V. Used with permission.NOTICE: this is the author’s version of a work that was accepted for publication in

Journal of Combinatorial Theory, Series B. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication.