Efficient computation of the oriented chromatic number of recursively defined digraphs
From MaRDI portal
Publication:2235732
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
oriented graphsefficient algorithmsparameterized algorithmsoriented coloringdirected clique-widthoriented co-graphsmsp-digraphs
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
