The complexity of signed graph and edge-coloured graph homomorphisms

DOI10.1016/J.DISC.2016.08.005zbMATH Open1351.05099arXiv1510.05502OpenAlexW2200162493MaRDI QIDQ2374178FDOQ2374178

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

Publication date: 14 December 2016

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

Abstract: We study homomorphism problems of signed graphs from a computational point of view. A signed graph $(G,Sigma)$ is a graph $G$ where each edge is given a sign, positive or negative; $SigmasubseteqE(G)$ denotes the set of negative edges. Thus, $(G,Sigma)$ is a $2$-edge-coloured graph with the property that the edge-colours, $+,-$, form a group under multiplication. Central to the study of signed graphs is the operation of switching at a vertex, that results in changing the sign of each incident edge. We study two types of homomorphisms of a signed graph $(G,Sigma)$ to a signed graph $(H,Pi)$: ec-homomorphisms and s-homomorphisms. Each is a standard graph homomorphism of $G$ to $H$ with some additional constraint. In the former, edge-signs are preserved. In the latter, edge-signs are preserved after the switching operation has been applied to a subset of vertices of $G$. We prove a dichotomy theorem for s-homomorphism problems for a large class of (fixed) target signed graphs $(H,Pi)$. Specifically, as long as $(H,Pi)$ does not contain a negative (respectively a positive) loop, the problem is polynomial-time solvable if the core of $(H,Pi)$ has at most two edges, and is NP-complete otherwise. (Note that this covers all simple signed graphs.) The same dichotomy holds if $(H,Pi)$ has no negative digons, and we conjecture that it holds always. In our proofs, we reduce s-homomorphism problems to certain ec-homomorphism problems, for which we are able to show a dichotomy. In contrast, we prove that a dichotomy theorem for ec-homomorphism problems (even when restricted to bipartite target signed graphs) would settle the dichotomy conjecture of Feder and Vardi.

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

Recommendations

• scientific article; zbMATH DE number 7650223
• The complexity of homomorphisms of signed graphs and signed constraint satisfaction
• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
• scientific article; zbMATH DE number 6269006
• Complexity of planar signed graph homomorphisms to cycles
• scientific article; zbMATH DE number 825134
• A complexity dichotomy for signed \(\mathbf{H}\)-colouring
• On colorings and orientations of signed graphs
• Edge coloring of signed graphs
• Complex and homomorphic chromatic number of signed planar simple graphs

zbMATH Keywords

graph homomorphismsigned graphedge-coloured graphdichotomy theorem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (26)

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

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

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