Recolouring Homomorphisms to triangle-free reflexive graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911788825575424 |
|---|---|
| author | Lee, Jae-baek Noel, Jonathan A. Siggers, Mark |
| author_facet | Lee, Jae-baek Noel, Jonathan A. Siggers, Mark |
| contents | For a graph $H$, the $H$-recolouring problem $\operatorname{Recol}(H)$ asks, for two given homomorphisms from a given graph $G$ to $H$, if one can get between them by a sequence of homomorphisms of $G$ to $H$ in which consecutive homomorphisms differ on only one vertex. We show that, if $G$ and $H$ are reflexive and $H$ is triangle-free, then this problem can be solved in polynomial time. This shows, at the same time, that the closely related $H$-reconfiguration problem $\operatorname{Recon}(H)$ of deciding whether two given homomorphisms from a given graph $G$ to $H$ are in the same component of the Hom-graph $\operatorname{Hom}(G,H)$, can be solved in polynomial time for triangle-free reflexive graphs $H$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_00723 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Recolouring Homomorphisms to triangle-free reflexive graphs Lee, Jae-baek Noel, Jonathan A. Siggers, Mark Combinatorics Primary 05C15, Secondary 05C85 For a graph $H$, the $H$-recolouring problem $\operatorname{Recol}(H)$ asks, for two given homomorphisms from a given graph $G$ to $H$, if one can get between them by a sequence of homomorphisms of $G$ to $H$ in which consecutive homomorphisms differ on only one vertex. We show that, if $G$ and $H$ are reflexive and $H$ is triangle-free, then this problem can be solved in polynomial time. This shows, at the same time, that the closely related $H$-reconfiguration problem $\operatorname{Recon}(H)$ of deciding whether two given homomorphisms from a given graph $G$ to $H$ are in the same component of the Hom-graph $\operatorname{Hom}(G,H)$, can be solved in polynomial time for triangle-free reflexive graphs $H$. |
| title | Recolouring Homomorphisms to triangle-free reflexive graphs |
| topic | Combinatorics Primary 05C15, Secondary 05C85 |
| url | https://arxiv.org/abs/2111.00723 |