Min Orderings and List Homomorphism Dichotomies for Signed and Unsigned Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10451828" target="_blank" >RIV/00216208:11320/22:10451828 - isvavai.cz</a>
Result on the web
<a href="https://link.springer.com/chapter/10.1007/978-3-031-20624-5_31" target="_blank" >https://link.springer.com/chapter/10.1007/978-3-031-20624-5_31</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-20624-5_31" target="_blank" >10.1007/978-3-031-20624-5_31</a>
Alternative languages
Result language
angličtina
Original language name
Min Orderings and List Homomorphism Dichotomies for Signed and Unsigned Graphs
Original language description
The CSP dichotomy conjecture has been recently established, but a number of other dichotomy questions remain open, including the dichotomy classification of list homomorphism problems for signed graphs. Signed graphs arise naturally in many contexts, including for instance nowhere-zero flows for graphs embedded in non-orientable surfaces. For a fixed signed graph ????^H^, the list homomorphism problem asks whether an input signed graph ????^G^ with lists ????(????)SUBSET OF OR EQUAL TO ????(????^),????ELEMENT OF????(????^),L(v)SUBSET OF OR EQUAL TOV(H^),vELEMENT OFV(G^), admits a homomorphism f to ????^H^ with all ????(????)ELEMENT OF????(????),????ELEMENT OF????(????^)f(v)ELEMENT OFL(v),vELEMENT OFV(G^).Usually, a dichotomy classification is easier to obtain for list homomorphisms than for homomorphisms, but in the context of signed graphs a structural classification of the complexity of list homomorphism problems has not even been conjectured, even though the classification of the complexity of homomorphism problems is known.Kim and Siggers have conjectured a structural classification in the special case of "weakly balanced" signed graphs. We confirm their conjecture for reflexive and irreflexive signed graphs; this generalizes previous results on weakly balanced signed trees, and weakly balanced separable signed graphs [1,2,3]. In the reflexive case, the result was first presented in [19], where the proof relies on a result in this paper. The irreflexive result is new, and its proof depends on first deriving a theorem on extensions of min orderings of (unsigned) bipartite graphs, which is interesting on its own.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Lecture Notes in Computer Science, vol 13568
ISBN
978-3-031-20623-8
ISSN
—
e-ISSN
—
Number of pages
17
Pages from-to
510-526
Publisher name
Springer
Place of publication
Berlin
Event location
Guanajuato, Mexico
Event date
Nov 7, 2022
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—