The complexity of signed graph and edge-coloured graph homomorphisms

DOI10.1016/J.DISC.2016.08.005MaRDI QIDQ2374178zbMATH OpenOpenAlexFDO

Authors Florent Foucaud, Reza Naserasr, 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

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)

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.

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

Cites work

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

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
• scientific article; zbMATH DE number 7559391 (Why is no real title available?)
• 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
• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
• Classification of edge-critical underlying absolute planar cliques for signed graphs
• List homomorphisms to separable signed graphs
• Density of \(C_{-4}\)-critical signed graphs
• Analogues of cliques for \((m,n)\)-colored mixed graphs
• Homomorphisms of sparse signed graphs
• Complexity of planar signed graph homomorphisms to cycles
• Towards a dichotomy for the list switch homomorphism problem for signed graphs
• 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
• Chromatic number and orientations of graphs and signed graphs
• On the packing number of antibalanced signed simple planar graphs of negative girth at least 5
• 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)