Complexity dichotomy for oriented homomorphism of planar graphs with large girth
DOI10.1016/J.TCS.2015.06.041zbMATH Open1328.68092OpenAlexW830674616MaRDI QIDQ2355705FDOQ2355705
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
Recommendations
- Homomorphism bounds for oriented planar graphs
- Homomorphism bounds for oriented planar graphs of given minimum girth
- scientific article
- 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
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)
Cites Work
- Title not available (Why is that?)
- Digraph width measures in parameterized algorithmics
- The Complexity of Multiterminal Cuts
- Colorings and girth of oriented planar graphs
- Homomorphisms and oriented colorings of equivalence classes of oriented graphs
- Homomorphisms from sparse graphs with large girth.
- On universal graphs for planar oriented graphs of a given girth
- New results on the complexity of oriented colouring on restricted digraph classes
- SOFSEM 2006: Theory and Practice of Computer Science
- A Complexity Dichotomy for the Coloring of Sparse Graphs
- Antisymmetric flows and strong colourings of oriented graphs
Cited In (9)
- The complexity of two graph orientation problems
- Pushable chromatic number of graphs with degree constraints
- Homomorphisms of planar \((m,n)\)-colored-mixed graphs to planar targets
- 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
- Complexity of planar signed graph homomorphisms to cycles
- The complexity of deciding whether a graph admits an orientation with fixed weak diameter
- On the pushable chromatic number of various types of grids
- On the Query Complexity of Testing Orientations for Being Eulerian
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)
