Journals
Resources
About Us
Open Access

Reconfiguration Graphs for Vertex Colorings of $P_5$-Free Graphs

Reconfiguration Graphs for Vertex Colorings of $P_5$-Free Graphs

Year:    2024

Author:    Hui Lei, Yulai Ma, Zhengke Miao, Yongtang Shi, Susu Wang

Annals of Applied Mathematics, Vol. 40 (2024), Iss. 4 : pp. 394–411

Abstract

For any positive integer $k,$ the reconfiguration graph for all $k$-colorings of a graph $G,$ denoted by $\mathcal{R}_k(G),$ is the graph where vertices represent the $k$-colorings of $G,$ and two $k$-colorings are joined by an edge if they differ in color on exactly one vertex. Bonamy et al. established that for any 2-chromatic $P_5$-free graph $G,$ $\mathcal{R}_k(G)$ is connected for each $k≥3.$ On the other hand, Feghali and Merkel proved the existence of a $7p$-chromatic $P_5$-free graph $G$ for every positive integer $p,$ such that $\mathcal{R}_{8p}(G)$ is disconnected.
In this paper, we offer a detailed classification of the connectivity of $\mathcal{R}_k(G)$ concerning $t$-chromatic $P_5$-free graphs $G$ for cases $t = 3,$ and $t ≥ 4$ with $t+1 ≤ k ≤(\begin{matrix} t \\ 2 \end{matrix}).$ We demonstrate that $\mathcal{R}_k(G)$ remains connected for each 3-chromatic $P_5$-free graph $G$ and each $k ≥4.$ Furthermore, for each $t≥4$ and $t+1\le k\le (\begin{matrix} t \\ 2 \end{matrix}),$ we provide a construction of a $t$-chromatic $P_5$-free graph $G$ with $\mathcal{R}_k(G)$ being disconnected. This resolves a question posed by Feghali and Merkel.

You do not have full access to this article.

Already a Subscriber? Sign in as an individual or via your institution

Journal Article Details

Publisher Name:    Global Science Press

Language:    English

DOI:    https://doi.org/10.4208/aam.OA-2024-0024

Annals of Applied Mathematics, Vol. 40 (2024), Iss. 4 : pp. 394–411

Published online:    2024-01

AMS Subject Headings:    Global Science Press

Copyright:    COPYRIGHT: © Global Science Press

Pages:    18

Keywords:    Reconfiguration graphs $P_5$-free graphs frozen colorings $k$-mixing.

Author Details

Hui Lei

Yulai Ma

Zhengke Miao

Yongtang Shi

Susu Wang