# Forbidden Directed Minors and Kelly-width

Today’s post is about the following paper, a joint work with Qiuyi Zhang, one of my advisees. Qiuyi Zhang is an undergraduate (rising senior) in our mathematics department.

• Shiva Kintali, Qiuyi Zhang. Forbidden Directed Minors and Kelly-width. (Preprint available on my publications page)

It is well-known that an undirected graph is a partial 1-tree (i.e., a forest) if and only if it has no $K_3$ minor. We generalized this characterization to partial 1-DAGs. We proved that partial 1-DAGs are characterized by three forbidden directed minors, $K_3, N_4$ and $M_5$, shown in the following figure. We named the last two graphs as $N_4$ and $M_5$ because their bidirected edges resemble the letters N and M.

Partial k-trees characterize bounded treewidth graphs. Similarly, partial k-DAGs characterize bounded Kelly-width digraphs. Kelly-width is the best known generalization of treewidth to digraphs.

As mentioned in the paper, I have a series of upcoming papers (called Directed Minors) making progress towards a directed graph minor theorem (i.e., all digraphs are well-quasi-ordered by the directed minor relation). For more details of the directed minor relation, read the current paper. I will post about the upcoming results as and when the preprints are ready.