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

DOI10.1016/J.DAM.2015.06.023zbMATH Open1327.05103OpenAlexW2173582843MaRDI QIDQ897592FDOQ897592

Authors: Sylvain Gravier, Hebert Coelho, Luerbio Faria, Sulamita Klein 

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

Recommendations

• SOFSEM 2006: Theory and Practice of Computer Science
• Oriented coloring on recursively defined digraphs
• Negative results on acyclic improper colorings
• On the oriented chromatic index of oriented graphs
• The complexity of the proper orientation number

zbMATH Keywords

bipartite graphNP-completeplanar graphoriented coloringmaximum degree 3 graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• On the oriented coloring of the disjoint union of graphs
• Convex circuit-free coloration of an oriented graph
• Efficient computation of the oriented chromatic number of recursively defined digraphs
• SOFSEM 2006: Theory and Practice of Computer Science
• Negative results on acyclic improper colorings
• Oriented colourings of graphs with maximum degree three and four

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

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