Improved Erdős-Pósa inequalities for odd cycles in planar graphs

Abstract

In an undirected graph, the odd cycle packing number is the maximum number of pairwise vertex-disjoint odd cycles. The odd cycle transversal number is the minimum number of vertices that hit every odd cycle. The maximum ratio between transversal and packing number is called Erdős-Pósa ratio. We show that in planar graphs, this ratio does not exceed 4. This improves on the previously best known bound of 6 by Král', Sereni and Stacho.

Summary

This research paper presents an improved Erdős-Pósa inequality for odd cycles in planar graphs, demonstrating that the ratio between the minimum odd cycle transversal and the maximum odd cycle packing is at most 4. This result refines our understanding of packing and covering problems and offers a constructive polynomial-time algorithm for computing these structures.

Key Insights

• •The paper establishes a tighter Erdős-Pósa bound of 4 for odd cycles in planar graphs, improving upon the previous bound of 6.
• •A novel structural lemma concerning 'F*-clouds' is introduced, enabling a recursive decomposition of the planar graph and a more refined analysis of odd cycle transversal and packing relationships.
• •The algorithm is constructive, meaning it provides a polynomial-time method for computing both an odd cycle transversal and an odd cycle packing with a guaranteed approximation ratio of 4.

Practical Implications

• •The improved approximation algorithm can be applied in practical scenarios where finding optimal odd cycle transversals or packings is computationally challenging, offering a guaranteed performance bound.
• •Future research could focus on closing the gap between the upper bound of 4 and the lower bound of 2 for the Erdős-Pósa ratio, potentially leading to even more efficient algorithms.
• •The techniques developed in this paper could potentially be extended to other classes of graphs beyond planar graphs, broadening the applicability of these results.

Links & Resources

Authors

Cite This Paper