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.

minors

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.

About these ads

2 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?

    • 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s