Forbidden directed minors and Kelly-width

详细信息    查看全文

• 作者：Shiva Kintali^a ; ^{kintali@cs.princeton.edu} ; Qiuyi Zhang^b ; ^{qiuyiz@princeton.edu}
• 关键词：Forbidden minors ; Graph minors ; Kelly-width ; Partial k-DAGs ; Treewidth
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：1 February 2017
• 年：2017
• 卷：662
• 期：Complete
• 页码：40-47
• 全文大小：337 K
• 卷排序：662

文摘

Partial k-DAGs are generalizations of partial k-trees. Partial k-trees are undirected graphs with bounded treewidth, whereas partial k  -DAGs are digraphs with bounded Kelly-width. It is well-known that an undirected graph is a partial 1-tree if and only if it has no K3K3 minor. In this paper, we prove that partial 1-DAGs are characterized by three forbidden directed minors, K3K3, N4N4 and M5M5.