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

DOI10.1016/J.DAM.2015.06.023MaRDI QIDQ897592zbMATHOpenAlexFDO

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

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)

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

Cites work

• Complexity of two coloring problems in cubic planar bipartite mixed graphs
• 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
• Node-and edge-deletion NP-complete problems
• On two coloring problems in mixed graphs
• Oriented graph coloring
• Partition into cliques for cubic graphs: Planar case, complexity and approximation
• SOFSEM 2006: Theory and Practice of Computer Science
• The Complexity of Colouring by Semicomplete Digraphs
• The chromatic number of oriented graphs
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures

Cited in

(11)

• Efficient computation of the oriented chromatic number of recursively defined digraphs
• On the oriented coloring of the disjoint union of graphs
• Oriented colourings of graphs with maximum degree three and four
• Complexity of the oriented coloring in planar, cubic oriented graphs
• Hardness transitions and uniqueness of acyclic colouring
• Convex circuit-free coloration of an oriented graph
• SOFSEM 2006: Theory and Practice of Computer Science
• The hardness of the functional orientation 2-color problem
• Negative results on acyclic improper colorings
• Oriented coloring on recursively defined digraphs
• Colorings of oriented planar graphs avoiding a monochromatic subgraph

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)