Claw-free graphs and 2-factors that separate independent vertices

✍ Scribed by Ralph J. Faudree; Colton Magnant; Kenta Ozeki; Kiyoshi Yoshimoto

• Book ID: 102339832
• Publisher: John Wiley and Sons
• Year: 2011
• Tongue: English
• Weight: 170 KB
• Volume: 69
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20579

✦ Synopsis

Abstract

In this article, we prove that a line graph with minimum degree δ≥7 has a spanning subgraph in which every component is a clique of order at least three. This implies that if G is a line graph with δ≥7, then for any independent set S there is a 2‐factor of G such that each cycle contains at most one vertex of S. This supports the conjecture that δ≥5 is sufficient to imply the existence of such a 2‐factor in the larger class of claw‐free graphs.

It is also shown that if G is a claw‐free graph of order n and independence number α with δ≥2__n__/α−2 and n≥3α^3^/2, then for any maximum independent set S, G has a 2‐factor with α cycles such that each cycle contains one vertex of S. This is in support of a conjecture that δ≥n/α≥5 is sufficient to imply the existence of a 2‐factor with α cycles, each containing one vertex of a maximum independent set. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 251–263, 2012