Induced 2-Regular Subgraphs in k-Chordal Cubic Graphs
classification
🧮 math.CO
keywords
fracinducedcubiccycleepsilongraphsleftlength
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.