Forbidden Directed Minors, Directed Path-Width and Directed Tree-Width of Tree-Like Digraphs

摘要

There have been many attempts to find directed graph classes with bounded directed path-width and bounded directed tree-width. Right now, the only known directed tree-width-/path-width-bounded graphs are cycle-free graphs with directed path-width and directed tree-width 0. In this paper, we introduce directed versions of cactus trees and pseudotrees and -forests and characterize them by at most three forbidden directed graph minors. Furthermore, we show that directed cactus trees and forests have a directed tree-width of at most 1 and directed pseudotrees and -forests even have a directed path-width of at most 1.