✦ LIBER ✦

Minimal acyclic forbidden minors for the family of graphs with bounded path-width

✍ Scribed by Atsushi Takahashi; Shuichi Ueno; Yoji Kajitani

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 732 KB
Volume: 127
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90092-2

No coin nor oath required. For personal study only.

✦ Synopsis

The graphs with bounded path-width, introduced by Robertson and Seymour, and the graphs with bounded proper-path-width, introduced in this paper, are investigated. These families of graphs are minor-closed.

We characterize the minimal acyclic forbidden minors for these families of graphs. We also give estimates for the numbers of minimal forbidden minors and for the numbers of vertices of the largest minimal forbidden minors for these families of graphs.