Extremal Graphs for Widom–Rowlinson Colorings in k-Chromatic Graphs

期刊论文
发表日期：

2024年11月28日

查看全文

John Engbers,
Aysel Erey

摘要

The Widom–Rowlinson graph, $H_{WR}$ $H_{WR}$ , is the fully looped path on three vertices. Let $\hom (G,H_{WR})$ $hom (G, H_{WR})$ be the number of graph homomorphisms from G to $H_{WR}$ $H_{WR}$ or, equivalently, the number of $H_{WR}$ $H_{WR}$ -colorings of G. We investigate extremal graphs for $\hom (G,H_{WR})$ $hom (G, H_{WR})$ for G in the family of k-chromatic graphs subject to various connectivity requirements. In particular, we determine the graphs G maximizing $\hom (G,H_{WR})$ $hom (G, H_{WR})$ in the families of n-vertex k-chromatic graphs, n-vertex connected k-chromatic graphs, n-vertex k-chromatic graphs with c components, n-vertex k-chromatic graphs without isolated vertices (for all n, k, c), and n-vertex k-chromatic $\ell $ $ℓ$ -connected, or minimum degree $\ell $ $ℓ$ , graphs (for all k and $\ell $ $ℓ$ , when n is large enough compared to k and $\ell $ $ℓ$ ). Lastly, we determine the graphs G minimizing $\hom (G,H_{WR})$ $hom (G, H_{WR})$ in n-vertex k-chromatic graphs and n-vertex graphs with connectivity $\ell $ $ℓ$ (for all $n,k,\ell $ $n, k, ℓ$ ), and in n-vertex 2-chromatic graphs with connectivity $\ell $ $ℓ$ (for all $\ell $ $ℓ$ , when n is large enough compared to $\ell $ $ℓ$ ).