Efficient computation of the oriented chromatic number of recursively defined digraphs

DOI10.1016/j.tcs.2021.08.013OpenAlexW3194877864MaRDI QIDQ2235732

Marvin Lindemann, Dominique Komander, Frank Gurski

Publication date: 21 October 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2012.13764

zbMATH Keywords

oriented graphsefficient algorithmsparameterized algorithmsoriented coloringdirected clique-widthoriented co-graphsmsp-digraphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Homomorphisms and colourings of oriented graphs: an updated survey
• Homomorphism bounds for oriented planar graphs of given minimum girth
• Fundamentals of parameterized complexity
• Parameterized algorithms for directed modular width
• Colourings of oriented connected cubic graphs
• Acyclic coloring parameterized by directed clique-width
• Are there any good digraph width measures?
• Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs
• Directed NLC-width
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Complement reducible graphs
• A partial k-arboretum of graphs with bounded treewidth
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Oriented colourings of graphs with maximum degree three and four
• Directed path-width and directed tree-width of directed co-graphs
• The dichromatic number of a digraph
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Oriented coloring on recursively defined digraphs
• On characterizations for subclasses of directed co-graphs
• Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs
• Computing digraph width measures on directed co-graphs (extended abstract)
• Oriented cliques and colorings of graphs with low maximum degree
• On width measures and topological problems on semi-complete digraphs
• Comparing linear width parameters for directed graphs
• The oriented chromatic number of Halin graphs
• The rank-width of edge-coloured graphs
• Digraph width measures in parameterized algorithmics
• Fully dynamic recognition algorithm and certificate for directed cographs
• Oriented coloring of msp-digraphs and oriented co-graphs (extended abstract)
• The Parameterized Complexity of Oriented Colouring
• Arc-Disjoint Paths in Decomposable Digraphs
• Integer Programming with a Fixed Number of Variables
• Intractability of Clique-Width Parameterizations
• Acyclic and oriented chromatic numbers of graphs
• Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract)
• New Results on the Complexity of Oriented Colouring on Restricted Digraph Classes
• Graph minors. II. Algorithmic aspects of tree-width
• The Recognition of Series Parallel Digraphs
• The chromatic number of oriented graphs
• Circular colorings of edge-weighted graphs
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• The circular chromatic number of a digraph
• A complete axiomatisation for the inclusion of series-parallel partial orders
• Classes of Directed Graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• On the Relationship Between Clique-Width and Treewidth
• Planar Digraphs of Digirth Four are 2-Colorable
• Digraphs
• SOFSEM 2006: Theory and Practice of Computer Science

This page was built for publication: Efficient computation of the oriented chromatic number of recursively defined digraphs