#### Document Type

Article

#### Language

eng

#### Format of Original

20 p.

#### Publication Date

6-2015

#### Publisher

Wiley

#### Source Publication

Journal of Graph Theory

#### Source ISSN

0364-9024

#### Original Item ID

doi: 10.1002/jgt.21820

#### Abstract

For graphs *G* and *H*, a homomorphism from *G* to *H*, or *H*-coloring of *G*, is a map from the vertices of *G* to the vertices of *H* that preserves adjacency. When *H* is composed of an edge with one looped endvertex, an *H*-coloring of *G* corresponds to an independent set in *G*. Galvin showed that, for sufficiently large *n*, the complete bipartite graph Κ is the *n*-vertex graph with minimum degree δ that has the largest number of independent sets. In this article, we begin the project of generalizing this result to arbitrary *H*. Writing hom(*G,H*) for the number of *H*-colorings of *G*, we show that for fixed *H* and δ=1 or δ=2,

hom*(G,H*) ≤max[hom(*Kσ+1, H)^(n/2σ), hom(Kσ,n-δ, H)]*

for any *n*-vertex *G* with minimum degree δ (for sufficiently large *n*). We also provide examples of *H* for which the maximum is achieved by and other *H* for which the maximum is achieved by hom(*Kσ+1, H)^(n/2σ)*. For δ≥3 (and sufficiently large *n*), we provide an infinite family of *H* for which hom*(G,H*)≤ hom(*Kσ*,n-*δ, H*) for any *n*-vertex *G* with minimum degree δ. The results generalize to weighted *H*-colorings.

## Comments

Accepted version.

Journal of Graph Theory, Vol. 79, No. 2 (June 2015): 103-124. DOI. © Wiley 2015. Used with permission.This is the peer reviewed version of the following article: Extremal

H-Colorings of Graphs with Fixed Minimum Degree. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.