Applications of matroid partition to tree decomposition

In this paper we present a matroid approach to the tree decomposition problem, give alternative proofs of the main results in 1,2], which give the necessary and sufficient conditions for a graphG=(V,E) of ordern to have a tree decomposition (T ₁,T ₂): (i)T _i is of ordern−1 and excludes the specified vertexu _i∈V, i=1,2; (ii)T ₁ is a spanning tree,T ₂ is of ordern−2 and excludes the specified verticesu ₁,u ₂∈V. As an application, we give a necessary and sufficient condition for a connected graph to have a tree-decomposition of {n−1,n−1∼ This research is partially supported by the National Natural Science Foundation of China.