A Generalization of an Ear Decomposition and k‐Trees in Highly Connected Star‐Free Graphs
Journal of Graph Theory · 30.10.2026
DOI: 10.1002/jgt.70153 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 30.10.2026. Verfasst von Shun‐ichi Maezawa und 3 weiteren Autor:innen. Die Arbeit nennt 17 Literaturangaben. Gefördert von: Japan Society for the Promotion of Science.
Abstract (Originalsprache)
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.
Förderung
- Japan Society for the Promotion of Science
Zitieren
APA
Maezawa, S., Ozeki, K., Yamamoto, M., & Yashima, T. (2026). A Generalization of an Ear Decomposition and k‐Trees in Highly Connected Star‐Free Graphs. Journal of Graph Theory. https://doi.org/10.1002/jgt.70153
Vancouver
Maezawa S, Ozeki K, Yamamoto M, Yashima T. A Generalization of an Ear Decomposition and k‐Trees in Highly Connected Star‐Free Graphs. Journal of Graph Theory. 2026. doi:10.1002/jgt.70153
BibTeX
@article{Maezawa2026,
author = {Maezawa, Shun‐ichi and Ozeki, Kenta and Yamamoto, Masaki and Yashima, Takamasa},
title = {A Generalization of an Ear Decomposition and k‐Trees in Highly Connected Star‐Free Graphs},
journal = {Journal of Graph Theory},
year = {2026},
doi = {10.1002/jgt.70153}
}
EUVIMED