Edge-disjoint odd cycles in planar graphs.

DOI10.1016/S0095-8956(03)00078-9zbMath1033.05064WikidataQ57601583 ScholiaQ57601583MaRDI QIDQ1425111

Daniel Král', Heinz-Juergen Voss

Publication date: 15 March 2004

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

zbMATH Keywords

Erdős-Pósa propertyBipartite graphsPlanar graphsOdd cycles

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (16)

Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation ⋮ Packing and Covering Immersion Models of Planar Subcubic Graphs ⋮ Negative (and positive) circles in signed graphs: a problem collection ⋮ The Erdős-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces ⋮ Approximate min-max relations on plane graphs ⋮ Packing and covering immersion-expansions of planar sub-cubic graphs ⋮ Recent techniques and results on the Erdős-Pósa property ⋮ Critical graphs for the chromatic edge-stability number ⋮ Approximate min-max relations for odd cycles in planar graphs ⋮ Packing and covering tetrahedra ⋮ An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\) ⋮ Planar graph bipartization in linear time ⋮ Packing and covering odd cycles in cubic plane graphs with small faces ⋮ Packing and covering odd cycles in cubic plane graphs with small faces ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Integer plane multiflow maximisation: one-quarter-approximation and gaps

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mangoes and blueberries
• The four-colour theorem
• On a conjecture of Tuza about packing and covering of triangles
• Optimal packings of edge-disjoint odd cycles
• A conjecture on triangles of graphs
• On Odd Cuts and Plane Multicommodity Flows
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• On Independent Circuits Contained in a Graph
• Node-and edge-deletion NP-complete problems
• A new proof and generalizations of a theorem of Erdős and Pósa on graphs withoutk+1 independent circuits
• The Erdős-Pósa property for odd cycles in highly connected graphs

This page was built for publication: Edge-disjoint odd cycles in planar graphs.