IEICE TRANSACTIONS on Fundamentals
Minimal Forbidden Minors for the Family of Graphs with Proper-Path-Width at Most Two
Summary :
The family Pk of graphs with proper-path-width at most k is minor-closed. It is known that the number of minimal forbidden minors for a minor-closed family of graphs is finite, but we have few such families for which all the minimal forbidden minors are listed. Although the minimal acyclic forbidden minors are characterized for Pk, all the minimal forbidden minors are known only for P1. This paper lists 36 minimal forbidden minors for P2, and shows that there exist no other minimal forbidden minors for P2.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E78-A No.12 pp.1828-1839
- Publication Date
- 1995/12/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Graphs and Networks
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Atsushi TAKAHASHI, Shuichi UENO, Yoji KAJITANI, "Minimal Forbidden Minors for the Family of Graphs with Proper-Path-Width at Most Two" in IEICE TRANSACTIONS on Fundamentals,
vol. E78-A, no. 12, pp. 1828-1839, December 1995, doi: .
Abstract: The family Pk of graphs with proper-path-width at most k is minor-closed. It is known that the number of minimal forbidden minors for a minor-closed family of graphs is finite, but we have few such families for which all the minimal forbidden minors are listed. Although the minimal acyclic forbidden minors are characterized for Pk, all the minimal forbidden minors are known only for P1. This paper lists 36 minimal forbidden minors for P2, and shows that there exist no other minimal forbidden minors for P2.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e78-a_12_1828/_p
Copy
@ARTICLE{e78-a_12_1828,
author={Atsushi TAKAHASHI, Shuichi UENO, Yoji KAJITANI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Minimal Forbidden Minors for the Family of Graphs with Proper-Path-Width at Most Two},
year={1995},
volume={E78-A},
number={12},
pages={1828-1839},
abstract={The family Pk of graphs with proper-path-width at most k is minor-closed. It is known that the number of minimal forbidden minors for a minor-closed family of graphs is finite, but we have few such families for which all the minimal forbidden minors are listed. Although the minimal acyclic forbidden minors are characterized for Pk, all the minimal forbidden minors are known only for P1. This paper lists 36 minimal forbidden minors for P2, and shows that there exist no other minimal forbidden minors for P2.},
keywords={},
doi={},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - Minimal Forbidden Minors for the Family of Graphs with Proper-Path-Width at Most Two
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1828
EP - 1839
AU - Atsushi TAKAHASHI
AU - Shuichi UENO
AU - Yoji KAJITANI
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E78-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 1995
AB - The family Pk of graphs with proper-path-width at most k is minor-closed. It is known that the number of minimal forbidden minors for a minor-closed family of graphs is finite, but we have few such families for which all the minimal forbidden minors are listed. Although the minimal acyclic forbidden minors are characterized for Pk, all the minimal forbidden minors are known only for P1. This paper lists 36 minimal forbidden minors for P2, and shows that there exist no other minimal forbidden minors for P2.
ER -
English
