TY - JOUR
T1 - Computing sharp 2-factors in claw-free graphs
AU - Broersma, Hajo
AU - Paulusma, Daniël
N1 - Conference code: 33
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ácek, 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ácek, Saito and Schelp.
U2 - 10.1016/j.jda.2009.07.001
DO - 10.1016/j.jda.2009.07.001
M3 - Article
SN - 1570-8667
VL - 8
SP - 321
EP - 329
JO - Journal of discrete algorithms
JF - Journal of discrete algorithms
IS - 3
M1 - 10.1016/j.jda.2009.07.001
T2 - 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008
Y2 - 25 August 2008 through 29 August 2008
ER -