High degree graphs contain large-star factors

Noga Alon; Nicholas Wormald

doi:10.1007/978-3-642-13580-4_1

High degree graphs contain large-star factors

Noga Alon, Nicholas Wormald

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

11 Citations (Scopus)

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 language	English
Title of host publication	Fete of Combinatorics and Computer Science
Pages	9-21
Number of pages	13
Volume	20
DOIs	https://doi.org/10.1007/978-3-642-13580-4_1
Publication status	Published - 2010
Externally published	Yes
Event	Meeting on Fete of Combinatorics and Computer Science - Keszthely, Hungary Duration: 11 Aug 2008 → 15 Aug 2008

Conference

Conference	Meeting on Fete of Combinatorics and Computer Science
Country/Territory	Hungary
City	Keszthely
Period	11/08/08 → 15/08/08

Access to Document

10.1007/978-3-642-13580-4_1

Cite this

@inproceedings{91333de81a7a40519978ea1a00f217e4,

title = "High degree graphs contain large-star factors",

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.",

author = "Noga Alon and Nicholas Wormald",

year = "2010",

doi = "10.1007/978-3-642-13580-4\_1",

language = "English",

isbn = "9783642135798",

volume = "20",

pages = "9--21",

booktitle = "Fete of Combinatorics and Computer Science",

note = "Meeting on Fete of Combinatorics and Computer Science ; Conference date: 11-08-2008 Through 15-08-2008",

}

TY - GEN

T1 - High degree graphs contain large-star factors

AU - Alon, Noga

AU - Wormald, Nicholas

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=78449286359&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-13580-4_1

DO - 10.1007/978-3-642-13580-4_1

M3 - Conference Paper

AN - SCOPUS:78449286359

SN - 9783642135798

VL - 20

SP - 9

EP - 21

BT - Fete of Combinatorics and Computer Science

T2 - Meeting on Fete of Combinatorics and Computer Science

Y2 - 11 August 2008 through 15 August 2008

ER -

High degree graphs contain large-star factors

Abstract

Conference

Access to Document

Other files and links

Cite this