Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs

Haitze J. Broersma, Daniël Paulusma, Kiyoshi Yoshimoto

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)

Abstract

Let $G$ be a claw-free graph with order $n$ and minimum degree $\delta$. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If $\delta = 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 $\delts \ge 5$, then $G$ has a 2-factor with at most $(n - 3)/(\delta - 1)$ components, unless $G$ is a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we cannot replace $\delta - 1$ by $\delta$, respectively.
Original languageUndefined
Article number10.1007/s00373-009-0855-7
Pages (from-to)427-460
Number of pages34
JournalGraphs and combinatorics
Volume25
Issue number4
DOIs
Publication statusPublished - 2009

Keywords

  • EWI-17516
  • IR-70041
  • METIS-265816

Cite this

Broersma, Haitze J. ; Paulusma, Daniël ; Yoshimoto, Kiyoshi. / Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs. In: Graphs and combinatorics. 2009 ; Vol. 25, No. 4. pp. 427-460.
@article{d8eef247cb70480fa2185ea893c34baa,
title = "Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs",
abstract = "Let $G$ be a claw-free graph with order $n$ and minimum degree $\delta$. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If $\delta = 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 $\delts \ge 5$, then $G$ has a 2-factor with at most $(n - 3)/(\delta - 1)$ components, unless $G$ is a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we cannot replace $\delta - 1$ by $\delta$, respectively.",
keywords = "EWI-17516, IR-70041, METIS-265816",
author = "Broersma, {Haitze J.} and Dani{\"e}l Paulusma and Kiyoshi Yoshimoto",
note = "10.1007/s00373-009-0855-7",
year = "2009",
doi = "10.1007/s00373-009-0855-7",
language = "Undefined",
volume = "25",
pages = "427--460",
journal = "Graphs and combinatorics",
issn = "0911-0119",
publisher = "Springer",
number = "4",

}

Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs. / Broersma, Haitze J.; Paulusma, Daniël; Yoshimoto, Kiyoshi.

In: Graphs and combinatorics, Vol. 25, No. 4, 10.1007/s00373-009-0855-7, 2009, p. 427-460.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs

AU - Broersma, Haitze J.

AU - Paulusma, Daniël

AU - Yoshimoto, Kiyoshi

N1 - 10.1007/s00373-009-0855-7

PY - 2009

Y1 - 2009

N2 - Let $G$ be a claw-free graph with order $n$ and minimum degree $\delta$. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If $\delta = 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 $\delts \ge 5$, then $G$ has a 2-factor with at most $(n - 3)/(\delta - 1)$ components, unless $G$ is a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we cannot replace $\delta - 1$ by $\delta$, respectively.

AB - Let $G$ be a claw-free graph with order $n$ and minimum degree $\delta$. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If $\delta = 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 $\delts \ge 5$, then $G$ has a 2-factor with at most $(n - 3)/(\delta - 1)$ components, unless $G$ is a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we cannot replace $\delta - 1$ by $\delta$, respectively.

KW - EWI-17516

KW - IR-70041

KW - METIS-265816

U2 - 10.1007/s00373-009-0855-7

DO - 10.1007/s00373-009-0855-7

M3 - Article

VL - 25

SP - 427

EP - 460

JO - Graphs and combinatorics

JF - Graphs and combinatorics

SN - 0911-0119

IS - 4

M1 - 10.1007/s00373-009-0855-7

ER -