On components of 2-factors in claw-free graphs

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

doi:10.1016/j.endm.2007.07.050

On components of 2-factors in claw-free graphs

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

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

10 Downloads (Pure)

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 language	Undefined
Title of host publication	EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications
Place of Publication	Amsterdam
Publisher	Elsevier
Pages	289-293
Number of pages	5
DOIs	https://doi.org/10.1016/j.endm.2007.07.050
Publication status	Published - Aug 2007
Event	EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications, Seville, Spain: EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications - Amsterdam Duration: 1 Aug 2007 → …

Publication series

Name	Electronic Notes in Discrete Mathematics
Publisher	Elsevier
Number	1
Volume	29
ISSN (Print)	1571-0653
ISSN (Electronic)	1571-0653

Conference

Conference	EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications, Seville, Spain
City	Amsterdam
Period	1/08/07 → …

Keywords

IR-62062
METIS-245869
EWI-11587

Access to Document

10.1016/j.endm.2007.07.050

http://eprints.eemcs.utwente.nl/secure2/11587/01/sdarticle.pdf

Cite this

@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 ; EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications, Seville, Spain ; Conference date: 01-08-2007",

year = "2007",

month = aug,

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, EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications, Seville, Spain, Amsterdam, 1/08/07. 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 proceeding › Conference contribution › Academic › peer-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

T2 - EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications, Seville, Spain

Y2 - 1 August 2007

ER -