2025/09/03 by Manoj Belavadi, Belavadi, Manoj, T. Karthick +1
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2509.03190
openalex publication_date 2025/09/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
For a graph G, let χ(G) denote the chromatic number of G. Given a graph G, the reconfiguration graph for the k-colorings of G, denoted by \cal Rk(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 \cal Rk(G) is connected, and is recolorable if it is k-mixing for all k> χ(G). In this paper, we give a complete characterization of (P2+P3, C4)-free graphs that are recolorable. Moreover, we show that if G is a recolorable (P2+P3, C4)-free graph, then for any k >χ(G), the diameter of \cal Rk(G) is at most 2n2. Furthermore, we show that if G is a (P2+P3, C4)-free graph on n vertices with degeneracy ρ(G), then for all k > ρ(G)+ 1, the diameter of \cal Rk(G) is at most O(n2). This confirms a conjecture of Cereceda for the class of (P2+P3, C4)-free graphs. These results generalize some known results available in the literature.