Complexity of planar signed graph homomorphisms to cycles

DOI10.1016/j.dam.2020.03.029zbMath1443.05084arXiv1907.03266OpenAlexW2953618197MaRDI QIDQ777377

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

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

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

Related Items (3)

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ Circular chromatic number of signed graphs ⋮ Density of \(C_{-4}\)-critical signed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms
• How colorful the signed graph?
• Homomorphisms and edge-colourings of planar graphs
• Dichotomy for bounded degree \(H\)-colouring
• 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
• Some simplified NP-complete graph problems
• Homomorphisms of edge-colored graphs and Coxeter groups
• Planar graphs with circular chromatic numbers between 3 and 4
• The complexity of colouring symmetric relational systems
• A mathematical bibliography of signed and gain graphs and allied areas
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Homomorphisms from sparse graphs with large girth.
• The complexity of \(H\)-colouring of bounded degree graphs
• A complexity dichotomy for signed \(\mathbf{H}\)-colouring
• High-girth graphs avoiding a minor are nearly bipartite
• The complexity of signed graph and edge-coloured graph homomorphisms
• Homomorphism bounds of signed bipartite \(K_4\)-minor-free graphs and edge-colorings of \(2k\)-regular \(K_4\)-minor-free multigraphs
• Tree-depth, subgraph coloring and homomorphism bounds
• 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
• Hypothetical complexity of the nowhere-zero 5-flow problem
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• Reducibility among Combinatorial Problems
• Homomorphisms of Signed Graphs
• Homomorphisms of 2‐Edge‐Colored Triangle‐Free Planar Graphs
• The star-chromatic number of planar 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: Complexity of planar signed graph homomorphisms to cycles