Reconfiguration graph for vertex colorings for ($P_2$+$P_3$, $C_4$)-free graphs

Abstract

For a graph $G$, let $\chi (G)$ denote the chromatic number of $G$. Given a graph $G$, the $reconfiguration$ $graph$ $for$ $the$ $k$-$colorings$ of $G$, denoted by ${\mathcal{R}}_k(G)$, is the graph whose vertices are the $k$-colorings of $G$ and two $k$-colorings are joined by an edge if they differ on exactly one vertex of $G$. A graph $G$ is $k$-$mixing$ if ${\mathcal{R}}_k(G)$ is connected, and is $recolorable$ if it is $k$-mixing for all $k>\chi (G)$. In this paper, we give a complete characterization of $(P_2+P_3,C_4)$-free graphs that are recolorable. Moreover, we show that if $G$ is a recolorable $(P_2+P_3,C_4)$-free graph, then for any $k>\chi (G)$, the diameter of ${\mathcal{R}}_k(G)$ is at most 2$n^2$. Furthermore, we show that if $G$ is a ($P_2+P_3,C_4$)-free graph on $n$ vertices with degeneracy $\rho (G)$, then for all $k>\rho (G)+1$, the diameter of ${\mathcal{R}}_k(G)$ is at most $O(n^2)$. This confirms a conjecture of Cereceda for the class of ($P_2+P_3,C_4$)-free graphs. These results generalize some known results available in the literature.

18 pages