Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs

DOI10.1016/J.DAM.2015.06.023zbMath1327.05103OpenAlexW2173582843MaRDI QIDQ897592

Sylvain Gravier, Sulamita Klein, Luérbio Faria, Hebert Coelho

Publication date: 7 December 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.06.023

zbMATH Keywords

bipartite graphNP-completeplanar graphoriented coloringmaximum degree 3 graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex degrees (05C07)

Related Items (2)

Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ On the oriented coloring of the disjoint union of graphs

Cites Work

• Partition into cliques for cubic graphs: Planar case, complexity and approximation
• Complexity of two coloring problems in cubic planar bipartite mixed graphs
• Good and semi-strong colorings of oriented planar graphs
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• On two coloring problems in mixed graphs
• New Results on the Complexity of Oriented Colouring on Restricted Digraph Classes
• The Complexity of Colouring by Semicomplete Digraphs
• The chromatic number of oriented graphs
• Node-and edge-deletion NP-complete problems
• SOFSEM 2006: Theory and Practice of Computer Science
• Oriented graph coloring

This page was built for publication: Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs