Complexity dichotomy for oriented homomorphism of planar graphs with large girth

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

zbMATH Keywords

NP-completenessplanar graphoriented homomorphism

Mathematics Subject Classification ID

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