Towards a dichotomy for the switch list homomorphism problem for signed graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909127439024128 |
|---|---|
| author | Kim, Hyobin Siggers, Mark |
| author_facet | Kim, Hyobin Siggers, Mark |
| contents | We make advances towards a structural characterisation of the signed graphs $H$ for which the list switch $H$-colouring problem $\operatorname{LSwHom}(H)$ problem is polynomial time solvable. We conjecture a characterisation for signed graphs that can be switched to graphs such that every negative edge is also positive, and prove the characterisation in the case that the signed graph is reflexive. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2104_07764 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Towards a dichotomy for the switch list homomorphism problem for signed graphs Kim, Hyobin Siggers, Mark Combinatorics 05C22 (Primary), 05C85 (Secondary) We make advances towards a structural characterisation of the signed graphs $H$ for which the list switch $H$-colouring problem $\operatorname{LSwHom}(H)$ problem is polynomial time solvable. We conjecture a characterisation for signed graphs that can be switched to graphs such that every negative edge is also positive, and prove the characterisation in the case that the signed graph is reflexive. |
| title | Towards a dichotomy for the switch list homomorphism problem for signed graphs |
| topic | Combinatorics 05C22 (Primary), 05C85 (Secondary) |
| url | https://arxiv.org/abs/2104.07764 |