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

作者：Chen Zhi Hong^*

来源：Graphs and Combinatorics, 2016, 32(2): 553-558.

DOI：10.1007/s00373-015-1608-4

• Cyclability
• Claw-free graphs
• Eulerian subgraphs
• Line 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 Ryjaek (J Comb Theory Ser B 70:217-224, 1997) closure concept, there is a -free graph G such that the closure . In this note, we prove that for a 3-connected claw-free graph H with its closure , 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 -free subgraph. This is an improvement of the main result in Gyori and Plummer (Stud Sci Math Hung 38:233-244, 2001).

• 出版日期2016-3