Computing sharp 2-factors in claw-free graphs

Broersma, H.J.; Paulusma, D.

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.

Citation

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

• Journal Article Type: Article
• Publication Date: Sep 1, 2010
• Deposit Date: Oct 6, 2010
• Publicly Available Date: Oct 7, 2010
• Journal: Journal of Discrete Algorithms
• Print ISSN: 1570-8667
• Electronic ISSN: 1570-8675
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 8
• Issue: 3
• Pages: 321-329
• DOI: https://doi.org/10.1016/j.jda.2009.07.001
• Keywords: Claw-free graph, 2-factor, Number of components, Polynomial algorithm.
• Public URL: https://durham-repository.worktribe.com/output/1538921