A generalization of an ear decomposition and k-trees in highly connected star-free graphs

Abstract

In this paper, we introduce a generalized version of an ear decomposition, called a $j$-spider decomposition, for $j$-connected star-free graphs with $j\ge 2$. Its application enables us to improve a previousely known sufficient condition for the existence of a $k$-tree in highly connected star-free graphs, where a $k$-tree is a spanning tree in which every vertex is of degree at most $k$. More precisely, we show that every $j$-connected $K_{1,j(k-2)+2}$-free graph has a $k$-tree for $k\ge j$, thereby improving a classical result of Jackson and Wormald for $k\ge j$. Our approach differs from previous studies based on toughness-type arguments and instead relies on both a~$j$-spider decomposition and a factor theorem related to Hall's marriage theorem.

12 pages, 1 figure