Approximate min-max relations on plane graphs
Jie Ma, Xingxing Yu, Wenan Zang · Journal of Combinatorial Optimization · 2011
Let G be a plane graph, let τ ( G ) (resp. τ ′( G )) be the minimum number of vertices (resp. edges) that meet all cycles of G , and let ν ( G ) (resp. ν ′( G )) be the maximum number of vertex-disjoint (resp. edge-disjoint) cycles in G . In this note we show that τ ( G )≤3 ν ( G ) and τ ′( G )≤4 ν ′( G )−1; our proofs are constructive, which yield polynomial-time algorithms for finding corresponding objects with the desired properties.