A characterization of partial 3‐trees
A. Satyanarayana, L. Tung · Networks · 1990
Abstract A k‐tree is defined recursively as follows: The complete graph Kk on k points is a k‐tree. Given a k‐tree G on n ≤ k points, a k‐tree on n + 1 points is obtained by adding a new point u and edges connecting u to every point of a Kk in G. A graph is a partial k‐tree if it is a subgraph of some k‐tree. In this paper, we establish some interesting properties of partial 3‐trees and show that a graph is a partial 3‐tree if and only if it has no subgraph contractible to K5, K2.2.2 C8(1, 4), or K2 ≤ C5. A graph G is said to be contractible to a graph H if H can be obtained from G by a sequence of edge contractions. hitherto, such a characterization of partial k‐trees was known only for the values of k ≤ 2.