Computing sharp 2-factors in claw-free graphs

Haitze J. Broersma, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

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�ek, Saito & Schelp.
Original languageUndefined
Title of host publication33rd International Symposium on Mathematical Foundations of Computer Science
Place of PublicationBerlin
PublisherSpringer
Pages193-204
Number of pages12
ISBN (Print)978-3-540-85237-7
DOIs
Publication statusPublished - Aug 2008
Event33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008: Mathematical Foundations of Computer Science - Torun, Poland, Torun, Poland
Duration: 25 Aug 200829 Aug 2008
Conference number: 33

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
NumberWoTUG-31
Volume5162
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008
Abbreviated titleMFCS 2008
CountryPoland
CityTorun
Period25/08/0829/08/08
OtherAugust 27-31, 2008

Keywords

  • EWI-14142
  • IR-62551
  • METIS-254914

Cite this

Broersma, H. J., & Paulusma, D. (2008). Computing sharp 2-factors in claw-free graphs. In 33rd International Symposium on Mathematical Foundations of Computer Science (pp. 193-204). [10.1007/978-3-540-85238-4_15] (Lecture Notes in Computer Science; Vol. 5162, No. WoTUG-31). Berlin: Springer. https://doi.org/10.1007/978-3-540-85238-4_15
Broersma, Haitze J. ; Paulusma, Daniël. / Computing sharp 2-factors in claw-free graphs. 33rd International Symposium on Mathematical Foundations of Computer Science. Berlin : Springer, 2008. pp. 193-204 (Lecture Notes in Computer Science; WoTUG-31).
@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}�?ek, Saito & Schelp.",
keywords = "EWI-14142, IR-62551, METIS-254914",
author = "Broersma, {Haitze J.} and Dani{\"e}l Paulusma",
note = "10.1007/978-3-540-85238-4_15",
year = "2008",
month = "8",
doi = "10.1007/978-3-540-85238-4_15",
language = "Undefined",
isbn = "978-3-540-85237-7",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
number = "WoTUG-31",
pages = "193--204",
booktitle = "33rd International Symposium on Mathematical Foundations of Computer Science",

}

Broersma, HJ & Paulusma, D 2008, Computing sharp 2-factors in claw-free graphs. in 33rd International Symposium on Mathematical Foundations of Computer Science., 10.1007/978-3-540-85238-4_15, Lecture Notes in Computer Science, no. WoTUG-31, 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, Haitze J.; Paulusma, Daniël.

33rd International Symposium on Mathematical Foundations of Computer Science. Berlin : Springer, 2008. p. 193-204 10.1007/978-3-540-85238-4_15 (Lecture Notes in Computer Science; Vol. 5162, No. WoTUG-31).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

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

AU - Broersma, Haitze J.

AU - Paulusma, Daniël

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

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�ek, 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�ek, Saito & Schelp.

KW - EWI-14142

KW - IR-62551

KW - METIS-254914

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 - 33rd International Symposium on Mathematical Foundations of Computer Science

PB - Springer

CY - Berlin

ER -

Broersma HJ, Paulusma D. Computing sharp 2-factors in claw-free graphs. In 33rd International Symposium on Mathematical Foundations of Computer Science. Berlin: Springer. 2008. p. 193-204. 10.1007/978-3-540-85238-4_15. (Lecture Notes in Computer Science; WoTUG-31). https://doi.org/10.1007/978-3-540-85238-4_15