2025/08/08 by Maezawa, Shun-ichi, Ozeki, Kenta, Yamamoto, Masaki +1
#05C05 #05C35 #05C40 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.05962
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 ≥ 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 K1,j(k-2)+2-free graph has a k-tree for k≥ j, thereby improving a classical result of Jackson and Wormald for k≥ 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.