Induced packing of odd cycles in planar graphs.

Abstract

An induced packing of odd cycles in a graph is a packing such that there is no edge in the graph between any two odd cycles in the packing. We prove that an induced packing of k odd cycles in an n-vertex graph can be found (if it exists) in time 2O(k3/2)⋅n2+ϵ (for any constant ϵ>0) when the input graph is planar. We also show that deciding if a graph has an induced packing of two odd induced cycles is NP-complete.