Reconfiguration graph for vertex colorings for ($P_2$+$P_3$, $C_4$)-free graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914345663856640 |
|---|---|
| author | Belavadi, M. Karthick, T. |
| author_facet | Belavadi, M. Karthick, T. |
| contents | 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 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 ${\cal R}_k(G)$ is connected, and is $recolorable$ if it is $k$-mixing for all $k> χ(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 >χ(G)$, the diameter of ${\cal 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 $ρ(G)$, then for all $k > ρ(G)+ 1$, the diameter of ${\cal 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_03190 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reconfiguration graph for vertex colorings for ($P_2$+$P_3$, $C_4$)-free graphs Belavadi, M. Karthick, T. Combinatorics 05C15 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 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 ${\cal R}_k(G)$ is connected, and is $recolorable$ if it is $k$-mixing for all $k> χ(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 >χ(G)$, the diameter of ${\cal 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 $ρ(G)$, then for all $k > ρ(G)+ 1$, the diameter of ${\cal 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. |
| title | Reconfiguration graph for vertex colorings for ($P_2$+$P_3$, $C_4$)-free graphs |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2509.03190 |