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

9 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 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
EventEuroComb 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

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

Conference

ConferenceEuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications, Seville, Spain
CityAmsterdam
Period1/08/07 → …

Keywords

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

Cite this