Computing sharp 2-factors in claw-free graphs

Hajo Broersma; Daniël Paulusma

doi:10.1016/j.jda.2009.07.001

Computing sharp 2-factors in claw-free graphs

Hajo Broersma, Daniël Paulusma

Research output: Contribution to journal › Article › Academic › peer-review

3 Citations (Scopus)

146 Downloads (Pure)

Abstract

In a previous 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 and Schelp.

Original language	English
Article number	10.1016/j.jda.2009.07.001
Pages (from-to)	321-329
Number of pages	9
Journal	Journal of discrete algorithms
Volume	8
Issue number	3
DOIs	https://doi.org/10.1016/j.jda.2009.07.001
Publication status	Published - Sept 2010
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

Access to Document

10.1016/j.jda.2009.07.001Licence: Other

ArticleFinal published version, 213 KBLicence: Other

3 Citations
1 Conference contribution

Computing sharp 2-factors in claw-free graphs
Broersma, H. & Paulusma, D., Aug 2008, Mathematical Foundations of Computer Science 2008: 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings. Ochmański, E. (ed.). Berlin: Springer, p. 193-204 12 p. (Lecture Notes in Computer Science; vol. 5162).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
2 Citations (Scopus)

2 Downloads (Pure)

Cite this

@article{564f547b0cd043e48221abb50eceb1bd,

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

abstract = "In a previous 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 and Schelp.",

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

year = "2010",

month = sep,

doi = "10.1016/j.jda.2009.07.001",

language = "English",

volume = "8",

pages = "321--329",

journal = "Journal of discrete algorithms",

issn = "1570-8667",

publisher = "Elsevier",

number = "3",

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

}

TY - JOUR

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

AU - Broersma, Hajo

AU - Paulusma, Daniël

N1 - Conference code: 33

PY - 2010/9

Y1 - 2010/9

N2 - In a previous 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 and Schelp.

AB - In a previous 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 and Schelp.

U2 - 10.1016/j.jda.2009.07.001

DO - 10.1016/j.jda.2009.07.001

M3 - Article

SN - 1570-8667

VL - 8

SP - 321

EP - 329

JO - Journal of discrete algorithms

JF - Journal of discrete algorithms

IS - 3

M1 - 10.1016/j.jda.2009.07.001

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

Access to Document

Fingerprint

Research output

Computing sharp 2-factors in claw-free graphs

Cite this