H. J. Broersma
Computing sharp 2-factors in claw-free graphs
Broersma, H. J.; Paulusma, D.
Authors
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
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
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search