Packing cycles through prescribed vertices
From MaRDI portal
Publication:2275896
DOI10.1016/j.jctb.2011.03.004zbMath1223.05231OpenAlexW2104713819MaRDI QIDQ2275896
Dániel Marx, Ken-ichi Kawarabayashi, Naonori Kakimura
Publication date: 10 August 2011
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.2011.03.004
Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
A tight Erdős-Pósa function for long cycles, Frames, $A$-Paths, and the Erdös--Pósa Property, Recent techniques and results on the Erdős-Pósa property, Towards a polynomial kernel for directed feedback vertex set, Kernels for deletion to classes of acyclic digraphs, Erdös-Pósa Property of Obstructions to Interval Graphs, An improved kernel for planar vertex-disjoint triangle packing, Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs, Even A‐cycles have the edge‐Erdős–Pósa property, \(K_4\)-expansions have the edge-Erdős-Pósa property, Erdős–Pósa property of obstructions to interval graphs, On the Erdős–Pósa Property for Long Holes in \(\boldsymbol{C_4}\)-Free Graphs, Erdős-Pósa property of chordless cycles and its applications, Degree conditions for the existence of vertex-disjoint cycles and paths: a survey, Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem, Packing cycles through prescribed vertices under modularity constraints, Chordless Cycle Packing Is Fixed-Parameter Tractable, The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs, Half-integral packing of odd cycles through prescribed vertices, Disjoint cycles intersecting a set of vertices, Unnamed Item, Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs, Parity Linkage and the Erdős-Pósa Property of Odd Cycles Through Prescribed Vertices in Highly Connected Graphs, Packing Cycles Faster Than Erdos--Posa, Erdös--Pósa Property for Labeled Minors: 2-Connected Minors, Parameterised algorithms for deletion to classes of DAGs, Graphs without two vertex-disjoint \(S\)-cycles, $K_4$-Subdivisions Have the Edge-Erdös--Pósa Property, Unnamed Item, Fixed-parameter tractability for subset feedback set problems with parity constraints
Cites Work
- Disjoint cycles intersecting a set of vertices
- Graph minors. V. Excluding a planar graph
- Packing directed circuits
- Graph minors. XIII: The disjoint paths problem
- On the odd-minor variant of Hadwiger's conjecture
- On the presence of disjoint subgraphs of a specified type
- Approximation algorithms and hardness results for cycle packing problems
- On Independent Circuits Contained in a Graph
- A new proof and generalizations of a theorem of Erdős and Pósa on graphs withoutk+1 independent circuits
