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 ‐spider decomposition, for ‐connected star‐free graphs with . This application enables us to improve a previously known sufficient condition for the existence of a ‐tree in highly connected star‐free graphs, where a ‐tree is a spanning tree in which every vertex is of degree at most . More precisely, we show that every ‐connected ‐free graph has a ‐tree for , thereby improving a classical result of Jackson and Wormald for . Our approach differs from previous studies based on toughness‐type arguments and instead relies on both a ‐spider decomposition and a factor theorem related to Hall's marriage theorem.