Abstract
| Original language | English |
|---|---|
| Article number | 10.1016/j.jda.2009.07.001 |
| Pages (from-to) | 321-329 |
| Number of pages | 9 |
| Journal | Journal of discrete algorithms |
| Volume | 8 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - Sep 2010 |
Fingerprint
Cite this
}
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 -