Complexity of planar signed graph homomorphisms to cycles

DOI10.1016/J.DAM.2020.03.029MaRDI QIDQ777377zbMATH OpenOpenAlexFDO

Authors François Dross, Florent Foucaud, Valia Mitsou, Pascal Ochem, Théo Pierron

Publication date 7 July 2020

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

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

zbMATH Keywords

graph homomorphismsigned graphplanar graphedge-coloured graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Signed and weighted graphs (05C22) Paths and cycles (05C38)

Abstract: We study homomorphism problems of signed graphs. A signed graph is an undirected graph where each edge is given a sign, positive or negative. An important concept for signed graphs is the operation of switching at a vertex, which is to change the sign of each incident edge. A homomorphism of a graph is a vertex-mapping that preserves the adjacencies; in the case of signed graphs, we also preserve the edge-signs. Special homomorphisms of signed graphs, called s-homomorphisms, have been studied. In an s-homomorphism, we allow, before the mapping, to perform any number of switchings on the source signed graph. This concept has been extensively studied, and a full complexity classification (polynomial or NP-complete) for s-homomorphism to a fixed target signed graph has recently been obtained. Such a dichotomy is not known when we restrict the input graph to be planar (not even for non-signed graph homomorphisms). We show that deciding whether a (non-signed) planar graph admits a homomorphism to the square $C_t^2$ of a cycle with $tge6$, or to the circular clique $K_{4t/(2t-1)}$ with $tge2$, are NP-complete problems. We use these results to show that deciding whether a planar signed graph admits an s-homomorphism to an unbalanced even cycle is NP-complete. (A cycle is unbalanced if it has an odd number of negative edges). We deduce a complete complexity dichotomy for the planar s-homomorphism problem with any signed cycle as a target. We also study further restrictions involving the maximum degree and the girth of the input signed graph. We prove that planar s-homomorphism problems to signed cycles remain NP-complete even for inputs of maximum degree~$3$ (except for the case of unbalanced $4$-cycles, for which we show this for maximum degree~$4$). We also show that for a given integer $g$, the problem for signed bipartite planar inputs of girth $g$ is either trivial or NP-complete.

Recommendations

• The complexity of signed graph and edge-coloured graph homomorphisms
• The complexity of homomorphisms of signed graphs and signed constraint satisfaction
• Complexity dichotomy for oriented homomorphism of planar graphs with large girth
• List homomorphism problems for signed trees
• Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$

Cites work

• scientific article; zbMATH DE number 4075098 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• A complexity dichotomy for signed \(\mathbf{H}\)-colouring
• A mathematical bibliography of signed and gain graphs and allied areas
• Characterizations of signed graphs
• Chromatic invariants of signed graphs
• Dichotomy for bounded degree \(H\)-colouring
• Edge-switching homomorphisms of edge-coloured graphs
• Graph theory with applications
• High-girth graphs avoiding a minor are nearly bipartite
• Homomorphism bounds of signed bipartite \(K_4\)-minor-free graphs and edge-colorings of \(2k\)-regular \(K_4\)-minor-free multigraphs
• Homomorphisms and edge-colourings of planar graphs
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Homomorphisms from sparse graphs with large girth.
• Homomorphisms of 2-edge-colored graphs
• Homomorphisms of 2-edge-colored triangle-free planar 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?
• Hypothetical complexity of the nowhere-zero 5-flow problem
• 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
• Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms
• Planar graphs with circular chromatic numbers between 3 and 4
• Reducibility among combinatorial problems
• Signed graph coloring
• Signed graphs
• Some simplified NP-complete graph problems
• 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
• The complexity of signed graph and edge-coloured graph homomorphisms
• The star-chromatic number of planar graphs
• Tree-depth, subgraph coloring and homomorphism bounds

Cited in

(9)

• The complexity of homomorphisms of signed graphs and signed constraint satisfaction
• Complexity dichotomy for oriented homomorphism of planar graphs with large girth
• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
• Towards a dichotomy for the list switch homomorphism problem for signed graphs
• List homomorphism problems for signed trees
• Density of \(C_{-4}\)-critical signed graphs
• The complexity of signed graph and edge-coloured graph homomorphisms
• Walk-powers and homomorphism bounds of planar signed graphs
• Circular chromatic number of signed graphs

This page was built for publication: Complexity of planar signed graph homomorphisms to cycles

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