List homomorphisms to separable signed graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910414867005440 |
|---|---|
| author | Bok, Jan Brewster, Richard Feder, Tomás Hell, Pavol Jedličková, Nikola |
| author_facet | Bok, Jan Brewster, Richard Feder, Tomás Hell, Pavol Jedličková, Nikola |
| contents | The complexity of the list homomorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees and reflexive signed graphs. Irreflexive signed graphs are in a certain sense the heart of the problem, as noted by a recent paper of Kim and Siggers. We focus on a special class of irreflexive signed graphs, namely those in which the unicoloured edges form a spanning path or cycle, which we call separable signed graphs. We classify the complexity of list homomorphisms to these separable signed graphs; we believe that these signed graphs will play an important role for the general resolution of the irreflexive case. We also relate our results to a conjecture of Kim and Siggers concerning the special case of semi-balanced irreflexive signed graphs; we have proved the conjecture in another paper, and the present results add structural information to that topic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_06449 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | List homomorphisms to separable signed graphs Bok, Jan Brewster, Richard Feder, Tomás Hell, Pavol Jedličková, Nikola Discrete Mathematics Combinatorics The complexity of the list homomorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees and reflexive signed graphs. Irreflexive signed graphs are in a certain sense the heart of the problem, as noted by a recent paper of Kim and Siggers. We focus on a special class of irreflexive signed graphs, namely those in which the unicoloured edges form a spanning path or cycle, which we call separable signed graphs. We classify the complexity of list homomorphisms to these separable signed graphs; we believe that these signed graphs will play an important role for the general resolution of the irreflexive case. We also relate our results to a conjecture of Kim and Siggers concerning the special case of semi-balanced irreflexive signed graphs; we have proved the conjecture in another paper, and the present results add structural information to that topic. |
| title | List homomorphisms to separable signed graphs |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2306.06449 |