Computing sharp 2-factors in claw-free graphs

Haitze J. Broersma; Daniël Paulusma

doi:10.1016/j.jda.2009.07.001

Computing sharp 2-factors in claw-free graphs

Haitze J. Broersma, Daniël Paulusma

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

3 Citations (Scopus)

24 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á�?ek, 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 - Sep 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

sdarticle
restricted
Final published version, 213 KBLicence: Other

Fingerprint Dive into the research topics of 'Computing sharp 2-factors in claw-free graphs'. Together they form a unique fingerprint.

Cite this

Broersma, H. J., & Paulusma, D. (2010). Computing sharp 2-factors in claw-free graphs. Journal of discrete algorithms, 8(3), 321-329. [10.1016/j.jda.2009.07.001]. https://doi.org/10.1016/j.jda.2009.07.001

@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}�?ek, Saito and Schelp.",

author = "Broersma, {Haitze J.} and Dani{\"e}l Paulusma",

year = "2010",

month = "9",

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

}

TY - JOUR

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

AU - Broersma, Haitze J.

AU - Paulusma, Daniël

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á�?ek, 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á�?ek, Saito and Schelp.

U2 - 10.1016/j.jda.2009.07.001

DO - 10.1016/j.jda.2009.07.001

M3 - Article

VL - 8

SP - 321

EP - 329

JO - Journal of discrete algorithms

JF - Journal of discrete algorithms

SN - 1570-8667

IS - 3

M1 - 10.1016/j.jda.2009.07.001

ER -