Induced 2-Regular Subgraphs in k-Chordal Cubic Graphs

2014/06/10 by Michael A. Henning, Henning, Michael A., Felix Joos +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1406.2438

10 pages

arxiv created 2014/06/10 · arxiv updated 2014/06/11

Abstract

We show that a cubic graph G of order n has an induced 2-regular subgraph of order at least a) (n-2)/(4-(4)/(k)), if G has no induced cycle of length more than k, b) (5n+6)/(8), if G has no induced cycle of length more than 4, and n>6, and c) ((1)/(4)+ε)n, if the independence number of G is at most ((3)/(8)-ε)n. To show the second result we give a precise structural description of cubic 4-chordal graphs.

Related

• Induced Cycles in Graphs
• Decycling cubic graphs
• On cyclically 4-connected cubic graphs
• Cycle double covers and non-separating cycles
• 2-Coupon Coloring of Cubic Graphs Containing 3-Cycle or 4-Cycle