Computing sharp 2-factors in claw-free graphs

Hajo Broersma, Daniël Paulusma

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

2 Citations (Scopus)


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 languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2008
Subtitle of host publication33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings
EditorsEdward Ochmański
Place of PublicationBerlin
Number of pages12
ISBN (Electronic)978-3-540-85238-4
ISBN (Print)978-3-540-85237-7
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
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008
Abbreviated titleMFCS 2008
OtherAugust 27-31, 2008


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

Cite this