Affordable Access

High degree graphs contain large-star factors

Authors
  • Alon, Noga
  • Wormald, Nicholas
Type
Preprint
Publication Date
Oct 11, 2008
Submission Date
Oct 11, 2008
Source
arXiv
License
Yellow
External links

Abstract

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 $\Omega((d/\log d)^{1/3})$. This settles a problem of J. Kratochvil.

Report this publication

Statistics

Seen <100 times