## THE CHVÁTAL-ERDOS CONDITION AND 2-FACTORS WITH A SPECIFIED NUMBER OF COMPONENTS

 Guantao Chen Department of Mathematics and Statistics Georgia State University, Atlanta, GA 30303, USA Ronald J. Gould Department of Mathematics and Computer Science Emory University, Atlanta, GA 30322, USA Ken-ichi Kawarabayashi National Institute of Informatics 2-1-2 Hitotsubashi, Chiyoda-Ku, Tokyo 101-8430, Japan Katsuhiro Ota Department of Mathematics, Keio University 3-14-1 Hiyoshi, Kohoku-Ku, Yokohama 223-8522, Japan Akira Saito Department of Computer Science, Nihon University Sakurajosui 3-25-40, Setagaya-Ku, Tokyo 156-8550, Japan Ingo Schiermeyer Institut für Diskrete Mathematik und Algebra Technische Universität Bergakademie Freiberg, D-09596 Freiberg, Germany

## Abstract

Let G be a 2-connected graph of order n satisfying α(G) = a ≤ κ(G), where α(G) and κ(G) are the independence number and the connectivity of G, respectively, and let r(m,n) denote the Ramsey number. The well-known Chvátal-Erdös Theorem states that G has a hamiltonian cycle. In this paper, we extend this theorem, and prove that G has a 2-factor with a specified number of components if n is sufficiently large. More precisely, we prove that (1) if n ≥ k·r(a+4, a+1), then G has a 2-factor with k components, and (2) if n ≥ r(2a+3, a+1)+3(k−1), then G has a 2-factor with k components such that all components but one have order three.

The Chvátal-Erdös Condition and 2-Factors with ...

Keywords: Chvátal-Erdös condition, 2-factor, hamiltonian cycle, Ramsey number.

2000 Mathematics Subject Classification: Primary: 05C38; Secondary: 05C40, 05C45, 05C69.

## References

 [1] A. Bondy, A remark on two sufficient conditions for Hamilton cycles, Discrete Math. 22 (1978) 191-194, doi: 10.1016/0012-365X(78)90124-3. [2] S. Brandt, G. Chen, R. Faudree, R. Gould and L. Lesniak, Degree conditions for 2-factors, J. Graph Theory 24 (1997) 165-173, doi: 10.1002/(SICI)1097-0118(199702)24:2<165::AID-JGT4>3.0.CO;2-O. [3] G. Chartrand and L. Lesniak, Graphs & Digraphs (3rd ed.) (Wadsworth & Brooks/Cole, Monterey, CA, 1996). [4] V. Chvátal and P. Erdös, A note on hamiltonian circuits, Discrete Math. 2 (1972) 111-113, doi: 10.1016/0012-365X(72)90079-9. [5] Y. Egawa, personal communication. [6] H. Enomoto, On the existence of disjoint cycles in a graph, Combinatorica 18 (1998) 487-492, doi: 10.1007/s004930050034. [7] A. Kaneko and K. Yoshimoto, A 2-factor with two components of a graph satisfying the Chvátal-Erdös condition, J. Graph Theory 43 (2003) 269-279, doi: 10.1002/jgt.10119. [8] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.