Complexity dichotomy for oriented homomorphism of planar graphs with large girth

DOI10.1016/J.TCS.2015.06.041MaRDI QIDQ2355705zbMATHOpenAlexFDO

Authors Guillaume Guégan, Pascal Ochem

Publication date 24 July 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.06.041

zbMATH Keywords

NP-completenessplanar graphoriented homomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Homomorphism bounds for oriented planar graphs
• Homomorphism bounds for oriented planar graphs of given minimum girth
• scientific article; zbMATH DE number 4162940
• The complexity of two graph orientation problems
• NP-Completeness of st-Orientations for Plane Graphs
• Complexity of planar signed graph homomorphisms to cycles
• NP-completeness of st-orientations for plane graphs
• The complexity of orientable graph manifolds
• scientific article; zbMATH DE number 4014763
• The Computational Complexity of Tutte Invariants for Planar Graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• Antisymmetric flows and strong colourings of oriented graphs
• Colorings and girth of oriented planar graphs
• Digraph width measures in parameterized algorithmics
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Homomorphisms from sparse graphs with large girth.
• New results on the complexity of oriented colouring on restricted digraph classes
• On universal graphs for planar oriented graphs of a given girth
• SOFSEM 2006: Theory and Practice of Computer Science
• The Complexity of Multiterminal Cuts

Cited in

(9)

• Homomorphisms of planar \((m,n)\)-colored-mixed graphs to planar targets
• On the pushable chromatic number of various types of grids
• Complexity of planar signed graph homomorphisms to cycles
• The complexity of two graph orientation problems
• Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\)
• The complexity of oblivious plans for orienting and distinguishing polygonal parts
• Pushable chromatic number of graphs with degree constraints
• On the Query Complexity of Testing Orientations for Being Eulerian
• The complexity of deciding whether a graph admits an orientation with fixed weak diameter

This page was built for publication: Complexity dichotomy for oriented homomorphism of planar graphs with large girth

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