On the recolorability of $(2K_2, K_4)$-free graphs

Abstract

Given a graph $G$ and an integer $\ell>χ(G)$, the reconfiguration graph of the $\ell$-colorings of $G$ has as its vertices as the proper $\ell$-colorings of $G$, with an edge between two colorings whenever they differ on exactly one vertex. We say that $G$ is \emph{recolorable} if this reconfiguration graph is connected for every $\ell>χ(G)$. Belavadi and Cameron determined which $(F_1,F_2)$-free graphs are recolorable whenever $F_1$ and $F_2$ are graphs on at most four vertices, with the single exception of $(2K_2,K_4)$-free graphs. Gaspers and Huang showed such graphs are $4$-colorable. The $3$-colorable case within this class has also been resolved, leaving the open question of whether every $(2K_2,K_4)$-free graph with chromatic number $4$ is recolorable. In this paper, we provide evidence toward an affirmative answer by establishing recolorability for three subclasses: $(2K_2,K_4,C_5)$-free graphs, $(2K_2,K_4,H_a,H_b)$-free graphs for any distinct $a,b\in \{2,3,4\}$, and $(2K_2,K_4,H_4)$-free graphs containing an induced $W_5$, where $H_i$ denotes the unique $2K_2$-free graph obtained from a $W_5$ by keeping exactly $i$ edges from the universal vertex to the cycle.

Disclosure

“stay funded by ANID Complementary Benefits and directed by Dr. Jessica McDonald at Auburn University. Declaration of use of artificial intelligence During the preparation of this manuscript the authors used OpenAI’s ChatGPT 5.5 Plus and Anthropic’s Claude to assist with editing, grammar, and formatting. The authors verified and reviewed all AI-assisted edits and take full responsibility for all content within this manuscript. References [1] M. Belavadi and K. Cameron. Recolouring some he”

PDF page 40

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-24T00:34:15.228Z

Structural counts