2025/04/11 by Masaki Kashima, Kashima, Masaki
Computer Science · Mathematics · #05C07 #05C38 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2504.08268
openalex publication_date 2025/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A claw-free graph is a graph that does not contain K1,3 as an induced subgraph, and a 2-factor is a 2-regular spanning subgraph of a graph. In 1997, Ryjáček introduced the closure concept of claw-free graphs, and Hamilton cycles and related structures in claw-free graphs have been intensively studied via the closure concept. In this paper, using the closure concept, we show that for a claw-free graph G of order n, if every independent set I of G satisfies |I|≤ δG(I)-1 and G satisfies σk+1(G)≥ n, then G has a 2-factor with at most k cycles, where δG(I) denotes the minimum degree of the vertices in I. As a corollary of the result, we show that every claw-free graph G with δ(G)≥ α(G)+1 has a 2-factor with at most α(G) cycles, which partially solves a conjecture by Faudree et al. in 2012.