Minimal acyclic forbidden minors for the family of graphs with bounded path-width
Minimal acyclic forbidden minors for the family of graphs with bounded path-width
复制标题
具有有限路径宽度的图族的最小非循环禁止次要子
DOI：
10.1016/0012-365x(94)90092-2
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Y. Kajitani
中科院分区：
文献类型：
--
作者：
A. Takahashi;S. Ueno;Y. Kajitani
研究了Robertson和Seymour提出的路宽有界的图和本文提出的固有路宽有界的图。这些图族都是小闭图。我们刻画了这些图族的最小无圈禁止未成年人。我们还估计了这些图族的最小禁止未成年人的数量和最大的最小禁止未成年人的顶点数。
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.