A Twelve Vertex Theorem for 3-Connected Claw-Free Graphs

The cyclability of a graph H, denoted by C(H), is the largest integer r such that H has a cycle through any r vertices. For a claw-free graph H, by Ryjá?ek (J Comb Theory Ser B 70:217–224, 1997) closure concept, there is a \(K_3\)-free graph G such that the closure \(cl(H)=L(G)\). In this note, we prove that for a 3-connected claw-free graph H with its closure \(cl(H)=L(G)\), \(C(H)\ge 12\) if and only if G can not be contracted to the Petersen graph in such a way that each vertex in P is obtained by contracting a nontrivial connected \(K_3\)-free subgraph. This is an improvement of the main result in Györi and Plummer (Stud Sci Math Hung 38:233–244, 2001).