The complexity of signed graph and edge-coloured graph homomorphisms

DOI10.1016/J.DISC.2016.08.005zbMath1351.05099arXiv1510.05502OpenAlexW2200162493MaRDI QIDQ2374178

Reza Naserasr, Florent Foucaud, Richard C. Brewster, Pavol Hell

Publication date: 14 December 2016

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

Full work available at URL: https://arxiv.org/abs/1510.05502

zbMATH Keywords

graph homomorphismsigned graphedge-coloured graphdichotomy theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)

Related Items (24)

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ Unnamed Item ⋮ Coloring problem of signed interval graphs ⋮ A complexity dichotomy for signed \(\mathbf{H}\)-colouring ⋮ Analogues of cliques for \((m,n)\)-colored mixed graphs ⋮ On the signed chromatic number of some classes of graphs ⋮ Homomorphism bounds of signed bipartite \(K_4\)-minor-free graphs and edge-colorings of \(2k\)-regular \(K_4\)-minor-free multigraphs ⋮ The 2-colouring problem for $(m,n)$-mixed graphs with switching is polynomial ⋮ List homomorphisms to separable signed graphs ⋮ Min orderings and list homomorphism dichotomies for signed and unsigned graphs ⋮ Chromatic polynomials of 2-edge-coloured graphs ⋮ On the packing number of antibalanced signed simple planar graphs of negative girth at least 5 ⋮ Unnamed Item ⋮ Homomorphisms of signed graphs: an update ⋮ Concepts of signed graph coloring ⋮ Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms ⋮ The complexity of tropical graph homomorphisms ⋮ Unnamed Item ⋮ Circular chromatic number of signed graphs ⋮ Chromatic number and orientations of graphs and signed graphs ⋮ Density of \(C_{-4}\)-critical signed graphs ⋮ Complexity of planar signed graph homomorphisms to cycles ⋮ Homomorphisms of sparse signed graphs ⋮ List homomorphism problems for signed trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How colorful the signed graph?
• Edge-switching homomorphisms of edge-coloured graphs
• On the complexity of \(H\)-colouring planar graphs
• On the complexity of H-coloring
• Signed graphs
• Signed graph coloring
• Chromatic invariants of signed graphs
• Homomorphisms of edge-colored graphs and Coxeter groups
• The complexity of colouring symmetric relational systems
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• The complexity of \(H\)-colouring of bounded degree graphs
• List homomorphisms and circular arc graphs
• On the notion of balance of a signed graph
• Characterizations of signed graphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Bi‐arc graphs and the complexity of list homomorphisms
• Homomorphisms of Signed Graphs
• The Complexity of Homomorphisms of Signed Graphs and Signed Constraint Satisfaction
• Homomorphisms of 2-edge-colored graphs
• On nice graphs

This page was built for publication: The complexity of signed graph and edge-coloured graph homomorphisms