Hostname: page-component-74656f9884-g96k6 Total loading time: 0 Render date: 2026-11-09T14:57:20.275Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimum Degree and Disjoint Cycles in Claw-Free Graphs

Published online by Cambridge University Press:  02 February 2012

RALPH J. FAUDREE ,
RONALD J. GOULD  and
MICHAEL S. JACOBSON
RALPH J. FAUDREE
Affiliation:
University of Memphis, Memphis, TN 38152, USA (e-mail: rfaudree@memphis.edu)
RONALD J. GOULD
Affiliation:
Emory University, Atlanta, GA 30322, USA (e-mail: rg@mathcs.emory.edu)
MICHAEL S. JACOBSON
Affiliation:
University of Colorado Denver, Denver, CO 80217, USA (e-mail: Michael.Jacobson@ucdenver.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A graph is claw-free if it does not contain an induced subgraph isomorphic to K1,3. Cycles in claw-free graphs have been well studied. In this paper we extend results on disjoint cycles in claw-free graphs satisfying certain minimum degree conditions. In particular, we prove that if G is claw-free of sufficiently large order n = 3k with δ(G) ≥ n/2, then G contains k disjoint triangles.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 1-2: Honouring the Memory of Richard H. Schelp , March 2012 , pp. 129 - 139
Copyright
Copyright © Cambridge University Press 2012

References

[1]Chen, G., Faudree, J. R., Gould, R. J. and Saito, A. (2000) 2-factors in claw-free graphs. Discuss. Math. Graph Theory 20 165–172.CrossRefGoogle Scholar
[2]Chen, G., Markus, L. and Schelp, R. (1995) Vertex disjoint cycles for star-free graphs. Australas. J. Combin. 11 157–167.Google Scholar
[3]Corradi, K. and Hajnal, A. (1963) On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar. 14 423–439.CrossRefGoogle Scholar
[4]Li, Y., Rousseau, C. and Zang, W. (2000) Asymptotic upper bounds for Ramsey functions. Graphs Combin. 17 123–128.CrossRefGoogle Scholar
[5]Wang, H. (1998) Vertex-disjoint triangles in claw-free graphs with minimum degree at least three. Combinatorica 18 441–447.CrossRefGoogle Scholar