On 2-Factors in r-Connected (K1, k, P4)-Free Graphs

Yoshimi Egawa, Jun Fujisawa, Shinya Fujita, Katsuhiro Ota

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


In [3], Faudree et al. considered the proposition “Every (X, Y)-free graph of sufficiently large order has a 2-factor,” and they determined those pairs (X, Y) which make this proposition true. Their result says that one of them is (X, Y) = (K1,4, P4). In this paper, we investigate the existence of 2-factors in r-connected (K1, k, P4)-free graphs. We prove that if r ≥ 1 and k ≥ 2, and if G is an r-connected (K1, k, P4)-free graph with minimum degree at least k − 1, then G has a 2-factor with at most max(k − r, 1) components unless (k − 1)K2 + (k − 2)K1 ⊆ G ⊆ (k − 1)K2 + Kk−2. The bound on the minimum degree is best possible.

Original languageEnglish
Pages (from-to)415-420
Number of pages6
JournalTokyo Journal of Mathematics
Issue number2
Publication statusPublished - 2008


  • 2-factor
  • Forbidden subgraph
  • Minimum degree

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'On 2-Factors in r-Connected (K1, k, P4)-Free Graphs'. Together they form a unique fingerprint.

Cite this