New Results on the Complexity of Oriented Colouring on Restricted Digraph Classes

DOI10.1007/978-3-642-11266-9_36zbMath1274.68138OpenAlexW1564136713MaRDI QIDQ3401108

Robert Ganian, Petr Hliněný

Publication date: 28 January 2010

Published in: SOFSEM 2010: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11266-9_36

zbMATH Keywords

complexitydirected graphoriented colouringDAG-depth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

Homomorphisms and colourings of oriented graphs: an updated survey ⋮ Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs ⋮ Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ On the oriented coloring of the disjoint union of graphs ⋮ Complexity dichotomy for oriented homomorphism of planar graphs with large girth

This page was built for publication: New Results on the Complexity of Oriented Colouring on Restricted Digraph Classes