Determining a graph from its reconfiguration graph
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_ | 1866908340511047680 |
|---|---|
| author | Berthe, Gaétan Brosse, Caroline Hearn, Brian Heuvel, Jan van den Hoppenot, Pierre Pierron, Théo |
| author_facet | Berthe, Gaétan Brosse, Caroline Hearn, Brian Heuvel, Jan van den Hoppenot, Pierre Pierron, Théo |
| contents | Given a graph $G$ and a natural number $k$, the $k$-recolouring graph $\mathcal{C}_k(G)$ is the graph whose vertices are the $k$-colourings of $G$ and whose edges link pairs of colourings which differ at exactly one vertex of $G$. Recently, Hogan et al. proved that $G$ can be determined from $\mathcal{C}_k(G)$ provided $k$ is large enough (quadratic in the number of vertices of $G$). We improve this bound by showing that $k=χ(G)+1$ colours suffice, and provide examples of families of graphs for which $k=χ(G)$ colours do not suffice.
We then extend this result to $k$-Kempe-recolouring graphs, whose vertices are again the $k$-colourings of a graph $G$ and whose edges link pairs of colourings which differ by swapping the two colours in a connected component induced by selecting those two colours. We show that $k=χ(G)+2$ colours suffice to determine $G$ in this case.
Finally, we investigate the case of independent set reconfiguration, proving that in only a few trivial cases is one guaranteed to be able to determine a graph $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_19783 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Determining a graph from its reconfiguration graph Berthe, Gaétan Brosse, Caroline Hearn, Brian Heuvel, Jan van den Hoppenot, Pierre Pierron, Théo Combinatorics Discrete Mathematics Given a graph $G$ and a natural number $k$, the $k$-recolouring graph $\mathcal{C}_k(G)$ is the graph whose vertices are the $k$-colourings of $G$ and whose edges link pairs of colourings which differ at exactly one vertex of $G$. Recently, Hogan et al. proved that $G$ can be determined from $\mathcal{C}_k(G)$ provided $k$ is large enough (quadratic in the number of vertices of $G$). We improve this bound by showing that $k=χ(G)+1$ colours suffice, and provide examples of families of graphs for which $k=χ(G)$ colours do not suffice. We then extend this result to $k$-Kempe-recolouring graphs, whose vertices are again the $k$-colourings of a graph $G$ and whose edges link pairs of colourings which differ by swapping the two colours in a connected component induced by selecting those two colours. We show that $k=χ(G)+2$ colours suffice to determine $G$ in this case. Finally, we investigate the case of independent set reconfiguration, proving that in only a few trivial cases is one guaranteed to be able to determine a graph $G$. |
| title | Determining a graph from its reconfiguration graph |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2504.19783 |