Complexity dichotomy for oriented homomorphism of planar graphs with large girth
From MaRDI portal
Publication:2355705
DOI10.1016/j.tcs.2015.06.041zbMath1328.68092OpenAlexW830674616MaRDI QIDQ2355705
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
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (4)
On the pushable chromatic number of various types of grids ⋮ Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\) ⋮ Pushable chromatic number of graphs with degree constraints ⋮ Homomorphisms of planar \((m,n)\)-colored-mixed graphs to planar targets
Cites Work
- Unnamed Item
- Antisymmetric flows and strong colourings of oriented graphs
- 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
- Digraph width measures in parameterized algorithmics
- New Results on the Complexity of Oriented Colouring on Restricted Digraph Classes
- The Complexity of Multiterminal Cuts
- A Complexity Dichotomy for the Coloring of Sparse Graphs
- SOFSEM 2006: Theory and Practice of Computer Science
This page was built for publication: Complexity dichotomy for oriented homomorphism of planar graphs with large girth