Skip to main content

Research Repository

Advanced Search

Computing sharp 2-factors in claw-free graphs

Broersma, H.J.; Paulusma, D.

Computing sharp 2-factors in claw-free graphs Thumbnail


Authors

H.J. Broersma



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 Mar 28, 2024
Journal Journal of Discrete Algorithms
Print ISSN 1570-8667
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

Files

Accepted Journal Article (187 Kb)
PDF

Copyright Statement
NOTICE: this is the author's version of a work that was accepted for publication in Journal of discrete algorithms.





You might also like



Downloadable Citations