Affordable Access

Publisher Website

On 2-factors in claw-free graphs

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
206
Identifiers
DOI: 10.1016/s0012-365x(98)00398-7
Disciplines
  • Mathematics

Abstract

Abstract A graph is said claw-free if it contains no induced subgraph isomorphic to K 1,3. We prove that if G is a claw-free graph with minimum degree δ⩾4, then G contains a 2-factor with at most 6 n/( δ+2)−1 components. Moreover, together with a theorem of Choudoum and Paulraj (J. Graph Theory 15 (1991) 259–265) and one of Anstee (J. Algorithms 6 (1985) 112–131), it is polynomial (in O( n 3)) to construct such a 2-factor.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

2-factors in claw-free graphs

on Electronic Notes in Discrete M... Dec 01, 2011

Path factors in claw-free graphs

on Discrete Mathematics Jan 01, 2002

Circumferences of 2-factors in claw-free graphs

on Discrete Mathematics Oct 06, 2013

Two-factors with few cycles in claw-free graphs

on Discrete Mathematics Jan 01, 2001
More articles like this..