H.J. Broersma
On components of 2-factors in claw-free graphs
Broersma, H.J.; Paulusma, D.; Yoshimoto, K.
Abstract
For a non-hamiltonian claw-free graph G with order n and minimum degree δ we show the following. If δ=4, then G has a 2-factor with at most (5n−14)/18 components, unless G belongs to a finite class of exceptional graphs. If δ⩾5, then G has a 2-factor with at most (n−3)/(δ−1) components. These bounds are sharp in the sense that we can replace nor 5/18 by a smaller quotient nor δ−1 by δ.
Citation
Broersma, H., Paulusma, D., & Yoshimoto, K. (2007). On components of 2-factors in claw-free graphs. Electronic Notes in Discrete Mathematics, 29, 289-293. https://doi.org/10.1016/j.endm.2007.07.050
Journal Article Type | Conference Paper |
---|---|
Conference Name | European Conference on Combinatorics, Graph Theory and Applications |
Publication Date | Aug 1, 2007 |
Deposit Date | Dec 21, 2014 |
Journal | Electronic Notes in Discrete Mathematics |
Print ISSN | 1571-0653 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 29 |
Pages | 289-293 |
DOI | https://doi.org/10.1016/j.endm.2007.07.050 |
Keywords | Claw-free graph, 2-factor, Minimum degree, Edge degree |
Public URL | https://durham-repository.worktribe.com/output/1153840 |
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
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
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(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