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.

3 thoughts on “Forbidden Directed Minors and Kelly-width”

1. If I google for “digraph minor”, the first hit is my old math.stackexchange question “Is there a useful definition of minors for digraphs?” The second answer (http://math.stackexchange.com/a/116449) contains many pictures, and the last picture illustrates a “typical” counterexample for an intuitive “directed graph minor theorem”.

I have also seen a presentation by Robin Thomas with a slide “DIGRAPH MINORS” containing the following statement: “QUESTION A For an infinite set of digraphs, is one a minor of another? HOPELESSLY FALSE”.

How does your notion of directed minor relation manages to work around these counterexamples which lead to the feeling that a “directed graph minor theorem” is hopeless?

• kintali |

In my paper available at arxiv.org/abs/1308.5170 , there is an operation called “Source Contraction”. Using this operation we can show that your counterexamples are well-quasi-ordered.