#### Document Type

Article

#### Language

eng

#### Publication Date

7-24-2013

#### Publisher

Cornell University Library

#### Source Publication

arXiv.org

#### 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 *K _{δ,n-δ}* is the

*n*-vertex graph with minimum degree

*δ*that has the largest number of independent sets.

In this paper, 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}^{⁄δ =1}, hom(

*K*

_{δ,δ}_{,}

*H*)

^{n⁄}

*hom(*

^{2δ},*K*)}

_{δ,n-δ,}Hfor any *n*-vertex *G* with minimum degree *δ* (for sufficiently large *n*). We also provide examples of *H* for which the maximum is achieved by hom(*K _{δ+1}*,

*H*)

^{n}^{⁄δ+1}and other

*H*for which the maximum is achieved by hom(

*K*)

_{δ,δ,}H

^{n}^{⁄2δ}

*.*For

*δ*≥ 3 (and sufficiently large

*n*), we provide a infinite family of

*H*for which hom(

*G*,

*H*) ≤ hom (

*K*H) for any

_{δ,n-δ},*n*-vertex

*G*with minimum degree

*δ*. The results generalize to weighted

*H*-colorings.

## Comments

Published version.

arXiv.org(July 24, 2013). Permalink. © The Author 2013. Used with permission.John Engbers was affiliated with the University of Notre Dame at the time of publication.