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

Authors

John Engbers, Marquette UniversityFollow
Aysel Erey, Utah State University

Document Type

Article

Publication Date

2024

Publisher

Springer

Source Publication

Graphs and Combinatorics

Source ISSN

0911-0119

Original Item ID

DOI: 10.1007/s00373-024-02869-3

Abstract

The Widom–Rowlinson graph, H_WR , is the fully looped path on three vertices. Let hom(G,H_WR) be the number of graph homomorphisms from G to H_WR or, equivalently, the number of H_WR-colorings of G. We investigate extremal graphs for 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) 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 ℓ-connected, or minimum degree ℓ, graphs (for all k and ℓ , when n is large enough compared to k and ℓ). Lastly, we determine the graphs G minimizing hom(G,H_WR) in n-vertex k-chromatic graphs and n-vertex graphs with connectivity ℓ (for all n, k, ℓ), and in n-vertex 2-chromatic graphs with connectivity ℓ (for all ℓ, when n is large enough compared to ℓ).

Comments

Accepted version. Graphs and Combinatorics, Vol. 40 (2024). DOI. © 2024 The Author(s), under exclusive licence to Springer Nature Japan KK. Used with permission.

Recommended Citation

Engbers, John and Erey, Aysel, "Extremal Graphs for Widom–Rowlinson Colorings in k-Chromatic Graphs" (2024). Mathematical and Statistical Science Faculty Research and Publications. 145.
https://epublications.marquette.edu/math_fac/145