Forbidden minors characterization of partial 3-trees. (English) Zbl 0701.05016

A partial k-tree is a subgraph of a graph that can be reduced to the complete graph of order k by a sequence of operations each being a removal of a degree k vertex with completely connected neighbours. In the paper the class of partial 3-trees is characterized by its set of four minimal forbidden minors.
Reviewer: P.Kirschenhofer


05C05 Trees


graph minors; trees
Full Text: DOI


[1] Arnborg, S., Reduced state enumeration—another algorithm for reliability evaluation, IEEE trans. reliability, R-27, 101-105, (1978) · Zbl 0436.60062
[2] Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability—a survey, Bit, 25, 2-33, (1985) · Zbl 0573.68018
[3] Arnborg, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. alg. and discr. methods, 8, 277-284, (1987) · Zbl 0611.05022
[4] Arnborg, S.; Proskurowski, A., Characterization and recognition of partial 3-trees, SIAM J. alg. and discr. methods, 7, 305-314, (1986) · Zbl 0597.05027
[5] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems on graphs embedded in k-trees, (), (to appear in Discr. Appl. Math., 1989)
[6] Colbourn, C.J.; Proskurowski, A., Concurrent transmissions in broadcast networks, (), 128-136, LNCS · Zbl 0554.94021
[7] Farley, A.M., Networks, immune to isolated failures, Networks, 11, 255-268, (1981) · Zbl 0459.94036
[8] Farley, A.M.; Proskurowski, A., Networks immune to isolated line failures, Networks, 12, 393-403, (1982) · Zbl 0493.94020
[9] Neufeld, E.M.; Colbourn, C.J., The most reliable series-parallel networks, TR 83-7, (1983), Dept. of Computing Science, University of Saskatchewan
[10] Proskurowski, A., Separating subgraphs in k-trees: cables and caterpillars, Discr. math., 49, 275-285, (1984) · Zbl 0543.05041
[11] Robertson, N.; Seymour, P.D., Disjoint paths—a survey, SIAM J. alg. discr. meth., 6, 300-305, (1985) · Zbl 0565.05045
[12] Wald, A.; Colbourn, C.J., Steiner trees, partial 2-trees, and minimum IFI networks, Networks, 13, 159-167, (1983) · Zbl 0529.68036
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.