Broersma, H.J. and Paulusma, Daniel (2008) 'Computing sharp 2-factors in claw-free graphs.', in Mathematical foundations of computer science 2008, 33rd International Symposium, MFCS 2008, 25-29 August 2008, Toru´n, Poland ; proceedings. Berlin ; Heidelberg: Springer, pp. 193-204. Lecture notes in computer science. (5162).
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áček, Saito & Schelp.
|Item Type:||Book chapter|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-540-85238-4_15|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||2008|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|