List homomorphism problems for signed trees

DOI10.1016/J.DISC.2022.113257zbMATH Open1506.05082OpenAlexW4310554412MaRDI QIDQ2111917FDOQ2111917

Jan Bok, Pavol Hell, Tomás Feder, Richard C. Brewster, Nikola Jedličková

Publication date: 17 January 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2022.113257

Recommendations

• The complexity of signed graph and edge-coloured graph homomorphisms
• The complexity of homomorphisms of signed graphs and signed constraint satisfaction
• Complexity of planar signed graph homomorphisms to cycles
• Bi‐arc graphs and the complexity of list homomorphisms
• The complexity of the list homomorphism problem for graphs

zbMATH Keywords

complexitygraph homomorphismsigned graphdichotomy

Mathematics Subject Classification ID

Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Signed graphs
• Signed graph coloring
• A mathematical bibliography of signed and gain graphs and allied areas
• On the notion of balance of a signed graph
• Title not available (Why is that?)
• On the complexity of H-coloring
• On the algebraic structure of combinatorial problems
• Monotone monadic SNP and constraint satisfaction
• List homomorphisms and circular arc graphs
• Absolute reflexive retracts and absolute bipartite retracts
• List homomorphisms to reflexive graphs
• Bi‐arc graphs and the complexity of list homomorphisms
• Characterizations of signed graphs
• Retractions to Pseudoforests
• The Complexity of Colouring by Semicomplete Digraphs
• Title not available (Why is that?)
• A simple algorithm to detect balance in signed graphs
• The complexity of signed graph and edge-coloured graph homomorphisms
• Edge-switching homomorphisms of edge-coloured graphs
• A complexity dichotomy for signed \(\mathbf{H}\)-colouring
• Homomorphisms of Signed Graphs
• The Complexity of Homomorphisms of Signed Graphs and Signed Constraint Satisfaction
• Homomorphisms of signed graphs: an update
• Title not available (Why is that?)
• The structure of bi-arc trees

Cited In (3)

• Min orderings and list homomorphism dichotomies for graphs and signed graphs
• Title not available (Why is that?)
• Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$

This page was built for publication: List homomorphism problems for signed trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2111917)