Extremal H-colorings of graphs with fixed minimum degree

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_{\delta ,n-\delta }$ is the $n$-vertex graph with minimum degree $\delta$ that has the largest number of independent sets. In this paper, we begin the project of generalizing this result to arbitrary $H$. Writing $\mathrm{hom}(G,H)$ for the number of $H$-colorings of $G$, we show that for fixed $H$ and $\delta =1$ or $\delta =2$, \[ \hom(G,H) \leq \max \{\hom(K_{δ+1},H)^{\frac{n}{δ+1}}, \hom(K_{δ,δ},H)^{\frac{n}{2δ}}, \hom(K_{δ,n-δ},H)\} \] for any $n$-vertex $G$ with minimum degree $\delta$ (for sufficiently large $n$). We also provide examples of $H$ for which the maximum is achieved by $\mathrm{hom}(K_{\delta +1},H{)}^{\frac{n}{\delta +1}}$ and other $H$ for which the maximum is achieved by $\mathrm{hom}(K_{\delta ,\delta },H{)}^{\frac{n}{2\delta }}$. For $\delta \ge 3$ (and sufficiently large $n$), we provide a infinite family of $H$ for which $\mathrm{hom}(G,H)\le \mathrm{hom}(K_{\delta ,n-\delta },H)$ for any $n$-vertex $G$ with minimum degree $\delta$. The results generalize to weighted $H$-colorings.

26 pages, 5 figures, final version

References in corpus (4)

• The Bipartite Swapping Trick on Graph Homomorphisms
• Maximizing the number of q-colorings
• Counting colorings of a regular graph
• The maximum number of complete subgraphs in a graph with given maximum degree