Computing the degreewidth of a digraph is hard

DOI10.46298/DMTCS.14299MaRDI QIDQ7364481zbMATH OpenFDO

Authors Pierre Aboulker, Nacim Oijid, Robin Petit, Mathis Rocton, Christopher-Lloyd Simon

Publication date 2 October 2026

Published in Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.46298/DMTCS.14299

Mathematics Subject Classification ID

Combinatorics (05-XX)

Cites work

• An analogue of Reed's conjecture for digraphs
• Degreewidth on semi-complete digraphs
• Degreewidth: A New Parameter for Solving Problems on Tournaments
• Eigenvalues and colorings of digraphs
• Exact and Approximate Digraph Bandwidth
• Four proofs of the directed Brooks' theorem
• Gallai's theorem for list coloring of digraphs
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order
• On width measures and topological problems on semi-complete digraphs
• Some results and problems on tournament structure
• The bandwidth problem for graphs and matrices—a survey
• The circular chromatic number of a digraph
• The dichromatic number of a digraph
• Tournament immersion and cutwidth
• Tournaments and colouring

This page was built for publication: Computing the degreewidth of a digraph is hard

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