Digraph coloring and distance to acyclicity

DOI10.1007/s00224-022-10103-xzbMATH Open1548.05144MaRDI QIDQ6614618

Ararat Harutyunyan, Nikolaos Melissinos, Michael Lampis

Publication date: 7 October 2024

Published in: Theory of Computing Systems (Search for Journal in Brave)

zbMATH Keywords

NP-completenessparameterized complexitydigraph coloringdichromatic numberfeedback vertex and arc sets

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• The dag-width of directed graphs
• On the algorithmic effectiveness of digraph decompositions and complexity measures
• Parameterized algorithms for directed modular width
• Acyclic coloring parameterized by directed clique-width
• Are there any good digraph width measures?
• Digraph measures: Kelly decompositions, games, and orderings
• Eigenvalues and colorings of digraphs
• Which problems have strongly exponential complexity?
• On directed feedback vertex set parameterized by treewidth
• Algorithmic meta-theorems for restrictions of treewidth
• The dichromatic number of a digraph
• Directed tree-width
• Colouring non-even digraphs
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Coloring tournaments: from local to global
• Subdivisions in digraphs of large out-degree or large dichromatic number
• Digraphs of bounded elimination width
• Parameterized Algorithms for Modular-Width
• Intractability of Clique-Width Parameterizations
• Uniquely D-colourable Digraphs with Large Girth
• A fixed-parameter algorithm for the directed feedback vertex set problem
• A Min-Max Theorem on Tournaments
• Circular colorings of edge-weighted graphs
• The circular chromatic number of a digraph
• Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
• Clique-width III
• List coloring digraphs
• On the Complexity of Digraph Colourings and Vertex Arboricity
• A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
• Perfect Digraphs
• Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
• Planar Digraphs of Digirth Four are 2-Colorable
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms

This page was built for publication: Digraph coloring and distance to acyclicity