On components of 2-factors in claw-free graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

For a non-hamiltonian claw-free graph $G$ with order $n$ and minimum degree $\delta$ we show the following. 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 $\delta \ge 5$, then $G$ has a 2-factor with at most $(n-3)/(\delta -1)$ components. These bounds are sharp in the sense that we can replace nor 5/18 by a smaller quotient nor $\delta -1$ by $\delta$.
Original languageUndefined
Title of host publicationEuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications
Place of PublicationAmsterdam
PublisherElsevier
Pages289-293
Number of pages5
DOIs
Publication statusPublished - Aug 2007

Publication series

NameElectronic Notes in Discrete Mathematics
PublisherElsevier
Number1
Volume29
ISSN (Print)1571-0653
ISSN (Electronic)1571-0653

Keywords

  • IR-62062
  • METIS-245869
  • EWI-11587

Cite this

Broersma, H. J., Paulusma, D., & Yoshimoto, K. (2007). On components of 2-factors in claw-free graphs. In EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications (pp. 289-293). [10.1016/j.endm.2007.07.050] (Electronic Notes in Discrete Mathematics; Vol. 29, No. 1). Amsterdam: Elsevier. https://doi.org/10.1016/j.endm.2007.07.050
Broersma, Haitze J. ; Paulusma, Daniël ; Yoshimoto, K. / On components of 2-factors in claw-free graphs. EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications. Amsterdam : Elsevier, 2007. pp. 289-293 (Electronic Notes in Discrete Mathematics; 1).
@inproceedings{f1c37ae6529146c6ba597619b379269c,
title = "On components of 2-factors in claw-free graphs",
abstract = "For a non-hamiltonian claw-free graph $G$ with order $n$ and minimum degree $\delta$ we show the following. 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 $\delta \ge 5$, then $G$ has a 2-factor with at most $(n-3)/(\delta -1)$ components. These bounds are sharp in the sense that we can replace nor 5/18 by a smaller quotient nor $\delta -1$ by $\delta$.",
keywords = "IR-62062, METIS-245869, EWI-11587",
author = "Broersma, {Haitze J.} and Dani{\"e}l Paulusma and K. Yoshimoto",
note = "10.1016/j.endm.2007.07.050",
year = "2007",
month = "8",
doi = "10.1016/j.endm.2007.07.050",
language = "Undefined",
series = "Electronic Notes in Discrete Mathematics",
publisher = "Elsevier",
number = "1",
pages = "289--293",
booktitle = "EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications",

}

Broersma, HJ, Paulusma, D & Yoshimoto, K 2007, On components of 2-factors in claw-free graphs. in EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications., 10.1016/j.endm.2007.07.050, Electronic Notes in Discrete Mathematics, no. 1, vol. 29, Elsevier, Amsterdam, pp. 289-293. https://doi.org/10.1016/j.endm.2007.07.050

On components of 2-factors in claw-free graphs. / Broersma, Haitze J.; Paulusma, Daniël; Yoshimoto, K.

EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications. Amsterdam : Elsevier, 2007. p. 289-293 10.1016/j.endm.2007.07.050 (Electronic Notes in Discrete Mathematics; Vol. 29, No. 1).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - On components of 2-factors in claw-free graphs

AU - Broersma, Haitze J.

AU - Paulusma, Daniël

AU - Yoshimoto, K.

N1 - 10.1016/j.endm.2007.07.050

PY - 2007/8

Y1 - 2007/8

N2 - For a non-hamiltonian claw-free graph $G$ with order $n$ and minimum degree $\delta$ we show the following. 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 $\delta \ge 5$, then $G$ has a 2-factor with at most $(n-3)/(\delta -1)$ components. These bounds are sharp in the sense that we can replace nor 5/18 by a smaller quotient nor $\delta -1$ by $\delta$.

AB - For a non-hamiltonian claw-free graph $G$ with order $n$ and minimum degree $\delta$ we show the following. 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 $\delta \ge 5$, then $G$ has a 2-factor with at most $(n-3)/(\delta -1)$ components. These bounds are sharp in the sense that we can replace nor 5/18 by a smaller quotient nor $\delta -1$ by $\delta$.

KW - IR-62062

KW - METIS-245869

KW - EWI-11587

U2 - 10.1016/j.endm.2007.07.050

DO - 10.1016/j.endm.2007.07.050

M3 - Conference contribution

T3 - Electronic Notes in Discrete Mathematics

SP - 289

EP - 293

BT - EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications

PB - Elsevier

CY - Amsterdam

ER -

Broersma HJ, Paulusma D, Yoshimoto K. On components of 2-factors in claw-free graphs. In EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications. Amsterdam: Elsevier. 2007. p. 289-293. 10.1016/j.endm.2007.07.050. (Electronic Notes in Discrete Mathematics; 1). https://doi.org/10.1016/j.endm.2007.07.050