Computing sharp 2-factors in claw-free graphs

Haitze J. Broersma, Daniël Paulusma

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

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 languageEnglish
Article number10.1016/j.jda.2009.07.001
Pages (from-to)321-329
Number of pages9
JournalJournal of discrete algorithms
Volume8
Issue number3
DOIs
Publication statusPublished - Sep 2010

Fingerprint

Claw-free Graphs
Byproducts
Computing
Number of Components
Polynomials
Polynomial Algorithm
Minimum Degree
Upper bound

Cite this

Broersma, Haitze J. ; Paulusma, Daniël. / Computing sharp 2-factors in claw-free graphs. In: Journal of discrete algorithms. 2010 ; Vol. 8, No. 3. pp. 321-329.
@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",

}

Computing sharp 2-factors in claw-free graphs. / Broersma, Haitze J.; Paulusma, Daniël.

In: Journal of discrete algorithms, Vol. 8, No. 3, 10.1016/j.jda.2009.07.001, 09.2010, p. 321-329.

Research output: Contribution to journalArticleAcademicpeer-review

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 -