Edge-disjoint odd cycles in 4-edge-connected graphs

DOI10.1016/j.jctb.2015.12.002zbMath1334.05072OpenAlexW2159406853MaRDI QIDQ273163

Ken-ichi Kawarabayashi, Yusuke Kobayashi

Publication date: 21 April 2016

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

Full work available at URL: https://doi.org/10.1016/j.jctb.2015.12.002

zbMATH Keywords

packingodd cycles4-edge-connected graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40)

Related Items

Coloring immersion-free graphs, Embedding mutually edge-disjoint cycles into locally twisted cubes, Recent techniques and results on the Erdős-Pósa property, Properly colored cycles of different lengths in edge-colored complete graphs, Packing and covering immersions in 4-edge-connected graphs, The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• Approximate min-max relations for odd cycles in planar graphs
• Highly parity linked graphs
• Graph minors. V. Excluding a planar graph
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Mangoes and blueberries
• Decomposition of regular matroids
• Disjoint paths in graphs
• 2-linked graphs
• Highly connected sets and the excluded grid theorem
• Primal-dual approximation algorithms for feedback problems in planar graphs
• Quickly excluding a planar graph
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph minors. XIII: The disjoint paths problem
• On the odd-minor variant of Hadwiger's conjecture
• A shorter proof of the graph minor algorithm
• Odd cycle packing
• On the Complexity of Timetable and Multicommodity Flow Problems
• Packing Digraphs with Directed Closed Trails
• Approximation algorithms and hardness results for cycle packing problems
• On Independent Circuits Contained in a Graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• The edge-disjoint paths problem is NP-complete for series-parallel graphs