2008/10/11 by Noga Alon, Alon, Noga, Nicholas Wormald +1
Computer Science · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.0810.2053
openalex publication_date 2008/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that any finite simple graph with minimum degree d contains a spanning star forest in which every connected component is of size at least Ω((d/log d)1/3). This settles a problem of J. Kratochvil.