High degree graphs contain large-star factors

Simple item page
dc.creatorAlon, Noga
dc.creatorWormald, Nicholas
dc.date2008-10-11
dc.date.accessioned2026-07-07T10:09:30Z
dc.date.available2026-07-07T10:09:30Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/0810.2053
dc.identifierhttp://arxiv.org/abs/0810.2053
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/171338
dc.subjectCombinatorics
dc.subject05C35
dc.titleHigh degree graphs contain large-star factors
dc.typetext

Files

Collections

arXiv