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 minor. We generalized this characterization to partial 1-DAGs. We proved that partial 1-DAGs are characterized by three forbidden **directed minors**, and , shown in the following figure. We named the last two graphs as and 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.

### Like this:

Like Loading...

*Related*

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?

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.