High degree graphs contain large-star factors

Noga Alon, Nicholas Wormald

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

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 Ω((d/log d)1/3). This settles a problem of Havet, Klazar, Kratochvil, Kratsch and Liedloff.

Original languageEnglish (US)
Title of host publicationFete of Combinatorics and Computer Science
Pages9-21
Number of pages13
DOIs
StatePublished - 2010
Externally publishedYes
EventMeeting on Fete of Combinatorics and Computer Science - Keszthely, Hungary
Duration: Aug 11 2008Aug 15 2008

Publication series

NameBolyai Society Mathematical Studies
Volume20
ISSN (Print)1217-4696
ISSN (Electronic)1217-4696

Other

OtherMeeting on Fete of Combinatorics and Computer Science
Country/TerritoryHungary
CityKeszthely
Period8/11/088/15/08

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'High degree graphs contain large-star factors'. Together they form a unique fingerprint.

Cite this