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. © 2015 Wiley. 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.

Download

Share

COinS