List homomorphism problems for signed trees

DOI10.1016/j.disc.2022.113257zbMath1506.05082OpenAlexW4310554412MaRDI QIDQ2111917

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

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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)

Related Items (2)

Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$ ⋮ Unnamed Item

Cites Work

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

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