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 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.

Comments

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

Available for download on Tuesday, January 01, 2019

Share

COinS