Computing sharp 2-factors in claw-free graphs

Hajo Broersma; Daniël Paulusma

doi:10.1007/978-3-540-85238-4_15

Computing sharp 2-factors in claw-free graphs

Hajo Broersma, Daniël Paulusma

Discrete Mathematics and Mathematical Programming

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

2 Citations (Scopus)

2 Downloads (Pure)

Abstract

In a recently submitted paper we obtained an upper bound for the minimum number of components of a 2-factor in a claw-free graph. This bound is sharp in the sense that there exist infinitely many claw-free graphs for which the bound is tight. In this paper we extend these results by presenting a polynomial algorithm that constructs a 2-factor of a claw-free graph with minimum degree at least four whose number of components meets this bound. As a byproduct we show that the problem of obtaining a minimum 2-factor (if it exists) is polynomially solvable for a subclass of claw-free graphs. As another byproduct we give a short constructive proof for a result of Ryjácek, Saito & Schelp.

Original language	English
Title of host publication	Mathematical Foundations of Computer Science 2008
Subtitle of host publication	33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings
Editors	Edward Ochmański
Place of Publication	Berlin
Publisher	Springer
Pages	193-204
Number of pages	12
ISBN (Electronic)	978-3-540-85238-4
ISBN (Print)	978-3-540-85237-7
DOIs	https://doi.org/10.1007/978-3-540-85238-4_15
Publication status	Published - Aug 2008
Event	33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008: Mathematical Foundations of Computer Science - Torun, Poland, Torun, Poland Duration: 25 Aug 2008 → 29 Aug 2008 Conference number: 33

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	5162
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008
Abbreviated title	MFCS 2008
Country/Territory	Poland
City	Torun
Period	25/08/08 → 29/08/08
Other	August 27-31, 2008

Access to Document

10.1007/978-3-540-85238-4_15

2 Citations
1 Article

Computing sharp 2-factors in claw-free graphs
Broersma, H. & Paulusma, D., Sept 2010, In: Journal of discrete algorithms. 8, 3, p. 321-329 9 p., 10.1016/j.jda.2009.07.001.
Research output: Contribution to journal › Article › Academic › peer-review

Open Access
File
3 Citations (Scopus)

133 Downloads (Pure)

Cite this

@inproceedings{bd941771c9b949eb93f1255f8d797b46,

title = "Computing sharp 2-factors in claw-free graphs",

abstract = "In a recently submitted paper we obtained an upper bound for the minimum number of components of a 2-factor in a claw-free graph. This bound is sharp in the sense that there exist infinitely many claw-free graphs for which the bound is tight. In this paper we extend these results by presenting a polynomial algorithm that constructs a 2-factor of a claw-free graph with minimum degree at least four whose number of components meets this bound. As a byproduct we show that the problem of obtaining a minimum 2-factor (if it exists) is polynomially solvable for a subclass of claw-free graphs. As another byproduct we give a short constructive proof for a result of Ryj{\'a}cek, Saito & Schelp.",

author = "Hajo Broersma and Dani{\"e}l Paulusma",

year = "2008",

month = aug,

doi = "10.1007/978-3-540-85238-4_15",

language = "English",

isbn = "978-3-540-85237-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "193--204",

editor = "Edward Ochma{\'n}ski",

booktitle = "Mathematical Foundations of Computer Science 2008",

address = "Germany",

note = "33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008 : Mathematical Foundations of Computer Science, MFCS 2008 ; Conference date: 25-08-2008 Through 29-08-2008",

}

Broersma, H & Paulusma, D 2008, Computing sharp 2-factors in claw-free graphs. in E Ochmański (ed.), Mathematical Foundations of Computer Science 2008: 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings. Lecture Notes in Computer Science, vol. 5162, Springer, Berlin, pp. 193-204, 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008, Torun, Poland, 25/08/08. https://doi.org/10.1007/978-3-540-85238-4_15

Computing sharp 2-factors in claw-free graphs. / Broersma, Hajo; Paulusma, Daniël.
Mathematical Foundations of Computer Science 2008: 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings. ed. / Edward Ochmański. Berlin: Springer, 2008. p. 193-204 (Lecture Notes in Computer Science; Vol. 5162).

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

TY - GEN

T1 - Computing sharp 2-factors in claw-free graphs

AU - Broersma, Hajo

AU - Paulusma, Daniël

N1 - Conference code: 33

PY - 2008/8

Y1 - 2008/8

N2 - In a recently submitted paper we obtained an upper bound for the minimum number of components of a 2-factor in a claw-free graph. This bound is sharp in the sense that there exist infinitely many claw-free graphs for which the bound is tight. In this paper we extend these results by presenting a polynomial algorithm that constructs a 2-factor of a claw-free graph with minimum degree at least four whose number of components meets this bound. As a byproduct we show that the problem of obtaining a minimum 2-factor (if it exists) is polynomially solvable for a subclass of claw-free graphs. As another byproduct we give a short constructive proof for a result of Ryjácek, Saito & Schelp.

AB - In a recently submitted paper we obtained an upper bound for the minimum number of components of a 2-factor in a claw-free graph. This bound is sharp in the sense that there exist infinitely many claw-free graphs for which the bound is tight. In this paper we extend these results by presenting a polynomial algorithm that constructs a 2-factor of a claw-free graph with minimum degree at least four whose number of components meets this bound. As a byproduct we show that the problem of obtaining a minimum 2-factor (if it exists) is polynomially solvable for a subclass of claw-free graphs. As another byproduct we give a short constructive proof for a result of Ryjácek, Saito & Schelp.

U2 - 10.1007/978-3-540-85238-4_15

DO - 10.1007/978-3-540-85238-4_15

M3 - Conference contribution

SN - 978-3-540-85237-7

T3 - Lecture Notes in Computer Science

SP - 193

EP - 204

BT - Mathematical Foundations of Computer Science 2008

A2 - Ochmański, Edward

PB - Springer

CY - Berlin

T2 - 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008

Y2 - 25 August 2008 through 29 August 2008

ER -

Computing sharp 2-factors in claw-free graphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Research output

Computing sharp 2-factors in claw-free graphs

Cite this