The parameterized complexity of oriented colouring

DOI10.4230/DROPS.MEMICS.2009.2350MaRDI QIDQ2917312zbMATH OpenOpenAlexFDO

Authors Robert Ganian

Publication date 28 September 2012

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2009/2350/pdf/09006.GanianRobert.2350.pdf/

zbMATH Keywords

graphsoriented colouringparameterized algorithmsrank-widthtree-width

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Recommendations

• New results on the complexity of oriented colouring on restricted digraph classes
• SOFSEM 2006: Theory and Practice of Computer Science
• Oriented coloring on recursively defined digraphs
• Efficient computation of the oriented chromatic number of recursively defined digraphs
• Digraph width measures in parameterized algorithmics

Cited in

(9)

• Parameterized mixed graph coloring
• Acyclic coloring parameterized by directed clique-width
• The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions
• A note on the parameterized complexity of unordered maximum tree orientation
• Efficient computation of the oriented chromatic number of recursively defined digraphs
• Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs
• Oriented coloring on recursively defined digraphs
• SOFSEM 2006: Theory and Practice of Computer Science
• New results on the complexity of oriented colouring on restricted digraph classes

This page was built for publication: The parameterized complexity of oriented colouring

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