Article ID Journal Published Year Pages File Type
419236 Discrete Applied Mathematics 2016 7 Pages PDF
Abstract

We show that a cubic graph GG of order nn has an induced 2-regular subgraph of order at least •n−24−4k, if GG has no induced cycle of length more than kk,•5n+68, if GG has no induced cycle of length more than 4, and n>6n>6, and•(14+ϵ)n, if the independence number of GG is at most (38−ϵ)n. To show the second result we give a precise structural description of cubic 4-chordal graphs.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,