Skip to main content

Research Repository

Advanced Search

Computing sharp 2-factors in claw-free graphs

Broersma, H. J.; Paulusma, D.

Authors

H. J. Broersma



Contributors

Edward Ochmanski
Editor

Jerzy Tyszkiewicz
Editor

Abstract

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.

Citation

Broersma, H. J., & Paulusma, D. (2008). Computing sharp 2-factors in claw-free graphs. In E. Ochmanski, & J. Tyszkiewicz (Eds.), Mathematical foundations of computer science 2008, 33rd International Symposium, MFCS 2008, 25-29 August 2008, Toru´n, Poland ; proceedings (193-204). https://doi.org/10.1007/978-3-540-85238-4_15

Conference Name 33th International Symposium on Mathematical Foundations of Computer Science
Conference Location Toru´n, Poland
Publication Date Jan 1, 2008
Deposit Date Oct 6, 2010
Publisher Springer Verlag
Pages 193-204
Series Title Lecture notes in computer science
Series Number 5162
Edition 33th
Book Title Mathematical foundations of computer science 2008, 33rd International Symposium, MFCS 2008, 25-29 August 2008, Toru´n, Poland ; proceedings.
DOI https://doi.org/10.1007/978-3-540-85238-4_15
Public URL https://durham-repository.worktribe.com/output/1158525


You might also like



Downloadable Citations