List homomorphism problems for signed trees

DOI10.1016/J.DISC.2022.113257MaRDI QIDQ2111917zbMATHOpenAlexFDO

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

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

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)

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

Cites work

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

Cited in

(5)

• The complexity of homomorphisms of signed graphs and signed constraint satisfaction
• Complexity of planar signed graph homomorphisms to cycles
• Min orderings and list homomorphism dichotomies for graphs and signed graphs
• Towards a dichotomy for the list switch homomorphism problem for signed graphs
• 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)