Induced 2-Regular Subgraphs in k-Chordal Cubic Graphs

Abstract

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

10 pages

References in corpus (2)

• A Dirac-type Characterization of k-chordal Graphs
• Induced Cycles in Graphs