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