×

zbMATH — the first resource for mathematics

Minimal acyclic forbidden minors for the family of graphs with bounded path-width. (English) Zbl 0795.05123
The authors characterize the minimal acyclic forbidden minors for the families \(F_ k\) and \(P_ k\) of graphs with path-width and proper path- width, respectively, at most \(k\). They also give estimates for the number of minimal forbidden minors for \(F_ k\) and \(P_ k\) and for the number of vertices in the largest minimal forbidden minors for \(F_ k\) and \(P_ k\).

MSC:
05C75 Structural characterization of families of graphs
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Archdeacon, D., A Kuratowski theorem for the projective plane, J. Graph Theory, 7, 325-334, (1983)
[2] Arnborg, S.; Corneil, D. G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. Algebraic Discrete Methods, 8, 277-284, (1987) · Zbl 0611.05022
[3] Arnborg, S.; Proskurowski, A.; Corneil, D. G., Forbidden minors characterization of partial 3-trees, Discrete Math., 80, 1-19, (1990) · Zbl 0701.05016
[4] Dai, W. W.; Sato, M., Minimal forbidden minor characterization of planar partial 3-trees and application to circuit layout, Proc. ISCAS, 2677-2681, (1990)
[5] Fellows, M. R.; Kinnersley, N. G.; Langston, M. A., Finite-basis theorems and a computational-integrated approach to obstruction set isolation, Proceedings of Computers and Mathematics Conference, (1989) · Zbl 0677.68039
[6] Fellows, M. R.; Langston, M. A., On search, decision and the efficiency of polynomial-time algorithms, Proc. 21st ACM Symp. on Theory of Computing, 501-512, (1989)
[7] Friedman, H.; Robertson, N.; Seymour, P. D., The metamathematics of the graph minor theorem, (Simpson, S. G., Logic and Combinatorics, AMS Contemporary Mathematics, 65, (1987), American Math. Soc Providence, RI), 229-261
[8] Fukuhara, T., Master’s thesis, (1990), Tokyo Institute of Technology
[9] Glover, H. H.; Huneke, P.; Wang, C., 103 graphs that are irreducible for the projective plane, J. Combin. Theory Ser. B, 27, 332-370, (1979) · Zbl 0352.05027
[10] Möhring, R. H., Graph problems related to gate matrix layout and PLA folding, (Tinhofer, G.; Mayr, E.; Noltemeier, H.; Syslo, M., Computational Graph Theory, (1990), Springer Wien New York), 17-51, Computing (Suppl. 7) · Zbl 0699.68072
[11] Parsons, T. D., Pursuit-evasion in a graph, (Alavi, Y.; Lick, D. R., Theory and Applications of Graphs, Lecture Notes in Mathematics, Vol. 642, (1976), Springer Berlin), 426-441
[12] Proskurowski, A., Separating subgraphs in k-trees: cables and caterpillars, Discrete Math., 49, 275-285, (1984) · Zbl 0543.05041
[13] Robertson, N.; Seymour, P. D., Graph minors, I. Excluding a forest, J. Combin. Theory Ser. B, 35, 39-61, (1983) · Zbl 0521.05062
[14] Robertson, N.; Seymour, P. D., The disjoint paths problem, Graph minors, XIII, (1986), preprint · Zbl 0598.05042
[15] Robertson, N.; Seymour, P. D., Graph minors, XVI. Wagner’s conjecture, (1987), preprint · Zbl 0568.05025
[16] Scheffler, P., A linear algorithm for the pathwidth of trees, (Bodendiek, R.; Henn, R., Topics in Combinatorics and Graph Theory, (1990), Physica Heidelberg), 613-620 · Zbl 0713.05025
[17] Takahashi, A.; Ueno, S.; Kajitani, Y., Mixed-searching and proper-path-width, (Hsu, W. L.; Lee, R. C.T., ISA ’91 Algorithms (Proc. 2nd Internat. Symp. on Algorithms, Taipei), Lecture Notes in Computer Science, Vol. 557, (1991), Springer Berlin), 61-71
[18] Takahashi, A.; Ueno, S.; Kajitani, Y., On the proper-path-decomposition of trees, (CAS 91-74, (1991), IEICE)
[19] Takahashi, A.; Ueno, S.; Kajitani, Y., Universal graphs for graphs with bounded path-width, SIGAL 91-24-3, IPSJ, Also Proc. Asia-Pacific Conf. on Circuits and Systems, 419-423, (1992), Sydney
[20] Takeuchi, M.; Soejima, S.; Kishimoto, W., A characterization of trees contained in a generalized Fan in terms of forbidden subgraphs, Trans. IEICE J75-A, 1216-1219, (1992), (in Japanese)
[21] Wagner, K., Bemerkung zu hadwigers vermutung, Math. Ann., 141, 433-451, (1960) · Zbl 0096.17904
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.