Tree decompositions for a class of graphs Original Research Article

For a graph G, if E(G) can be partitioned into several pairwise disjoint sets as {E1, E2,…, E1} such that for any i with 1 ⩽ i ⩽ l, the subgraph induced by E1 in G is a tree of order ki, then G is said to have a {k1, k2, … , k1}-tree-decomposition. Ringel [3], and Ouyang and Liu [2] proved that every 2-connected maximal planar bipartite (mpb) graph of order n has a {n − 1, n − 1}-tree-decomposition and {n,n − 2}-tree-decomposition, respectively. Kampen [1] proved that every maximal planar (mp) graph of order n has a {n − 1, n − 1, n − 1}-tree-decomposition. In this paper, we consider the following class of graphs including mpb and mp graphs: A graph G is called a Pk-graph, if if |G| ⩾ 3, |E(G)| = k(|G| −2) and |E(H)|⩽k(|H| −2) for any subgraph H of G with |H| ⩾ 3. We prove that (i) for any P2-graph of order n ⩾ 3, it has both a {n,n − 2}-tree-decomposition and a {n − 1, n − 1}-tree-decomposition, and moreover, these two kinds of tree-decompositions can be transformed to each other; (ii) for any P3-graph of order n ⩾ 4, it has three kinds of tree-decompositions: {n, n, n − 3}-, {n, n − 1, n − 2}- and {n − 1, n − 1, n − 1}-tree-decomposition, and moreover, they can be transformed to each other. Since 2-connected mpb graphs are P2-graphs and mp graphs are P3-graphs, the results mentioned above from [1–3] are immediately implied by our results. Furthermore, all tree-decompositions above can be found in polynomial time.