Recoloring via modular decomposition
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914335343771648 |
|---|---|
| author | Belavadi, Manoj Cameron, Kathie Sintiari, Ni Luh Dewi |
| author_facet | Belavadi, Manoj Cameron, Kathie Sintiari, Ni Luh Dewi |
| contents | The reconfiguration graph of the $k$-colorings of a graph $G$, denoted $R_{k}(G)$, is the graph whose vertices are the $k$-colorings of $G$ and two colorings are adjacent in $R_{k}(G)$ if they differ in color on exactly one vertex. A graph $G$ is said to be recolorable if $R_{\ell}(G)$ is connected for all $\ell \geq χ(G)$+1. We demonstrate how to use the modular decomposition of a graph class to prove that the graphs in the class are recolorable. In particular, we prove that every ($P_5$, diamond)-free graph, every ($P_5$, house, bull)-free graph, and every ($P_5$, $C_5$, co-fork)-free graph is recolorable.
A graph is prime if it cannot be decomposed by modular decomposition except into single vertices. For a prime graph $H$, we study the complexity of deciding if $H$ is $k$-colorable and the complexity of deciding if there exists a path between two given $k$-colorings in $R_{k}(H)$. Suppose $\mathcal{G}$ is a hereditary class of graphs. We prove that if every blowup of every prime graph in $\mathcal{G}$ is recolorable, then every graph in $\mathcal{G}$ is recolorable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_06446 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Recoloring via modular decomposition Belavadi, Manoj Cameron, Kathie Sintiari, Ni Luh Dewi Combinatorics Discrete Mathematics 05C15 The reconfiguration graph of the $k$-colorings of a graph $G$, denoted $R_{k}(G)$, is the graph whose vertices are the $k$-colorings of $G$ and two colorings are adjacent in $R_{k}(G)$ if they differ in color on exactly one vertex. A graph $G$ is said to be recolorable if $R_{\ell}(G)$ is connected for all $\ell \geq χ(G)$+1. We demonstrate how to use the modular decomposition of a graph class to prove that the graphs in the class are recolorable. In particular, we prove that every ($P_5$, diamond)-free graph, every ($P_5$, house, bull)-free graph, and every ($P_5$, $C_5$, co-fork)-free graph is recolorable. A graph is prime if it cannot be decomposed by modular decomposition except into single vertices. For a prime graph $H$, we study the complexity of deciding if $H$ is $k$-colorable and the complexity of deciding if there exists a path between two given $k$-colorings in $R_{k}(H)$. Suppose $\mathcal{G}$ is a hereditary class of graphs. We prove that if every blowup of every prime graph in $\mathcal{G}$ is recolorable, then every graph in $\mathcal{G}$ is recolorable. |
| title | Recoloring via modular decomposition |
| topic | Combinatorics Discrete Mathematics 05C15 |
| url | https://arxiv.org/abs/2405.06446 |