This is a short post about the following paper :
- Shiva Kintali. “Directed Width Parameters and Circumference of Digraphs“. Preprint available on my publications page.
We prove that the directed treewidth, DAG-width and Kelly-width of a digraph are bounded above by its circumference plus one. This generalizes a theorem of Birmele stating that the treewidth of an undirected graph is at most its circumference.
Theorem : Let G be a digraph of circumference l. Then the directed treewidth, DAG-width and Kelly-width of G are at most l + 1.
The above theorem can be seen as a mini mini mini directed grid minor theorem. I will be using this theorem in future papers to make progress towards a directed grid minor theorem. Stay tuned !!