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)
    9 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 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
    Event33rd 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

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

    }

    Broersma, HJ & Paulusma, D 2010, 'Computing sharp 2-factors in claw-free graphs', Journal of discrete algorithms, vol. 8, no. 3, 10.1016/j.jda.2009.07.001, pp. 321-329. https://doi.org/10.1016/j.jda.2009.07.001

    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 journal › Article › Academic › peer-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 -

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

    Access to Document