Computing sharp 2-factors in claw-free graphs

Hajo Broersma, Daniël Paulusma

    Research output: Contribution to journalArticleAcademicpeer-review

    3 Citations (Scopus)
    105 Downloads (Pure)


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


    Dive into the research topics of 'Computing sharp 2-factors in claw-free graphs'. Together they form a unique fingerprint.
    • 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 proceedingConference contributionAcademicpeer-review

      2 Citations (Scopus)

    Cite this