Forbidden Minors Characterization of Partial 3-trees
Stefan Arnborg, Andrzej Proakurowaki, Derek Corneil
Committee:
Technical Report(Jul 1986)
Keywords:

A k-tree is formed from a k-complete graph by recursively adding a vertex adjacent to all vertices in an existing k-complete subgraph. The many applications of partial k-trees (subgraphs of k-trees) have motivated their study from both the algorithmic and theoretical points of view. In this paper we characterize the class of partial 3-trees by its set of four minimal forbidden minors (His a minor of G if H can be obtained from G by a finite sequence of edge-extraction and edge-contraction operations.)