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 !!

### Like this:

Like Loading...