Disjoint cycles intersecting a set of vertices

DOI10.1016/j.jctb.2012.05.004zbMath1252.05097OpenAlexW2075199819MaRDI QIDQ713977

D. Kharzeev

Publication date: 19 October 2012

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.2012.05.004

zbMATH Keywords

graphpackingdisjoint cycles\(S\)-cycles

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Generalized Ramsey theory (05C55)

Related Items (29)

The edge-Erdős-Pósa property ⋮ 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 ⋮ 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 ⋮ Erdős-Pósa property of chordless cycles and its applications ⋮ Degree conditions for the existence of vertex-disjoint cycles and paths: a survey ⋮ Packing cycles through prescribed vertices under modularity constraints ⋮ Erdös--Pósa from Ball Packing ⋮ Chordless Cycle Packing Is Fixed-Parameter Tractable ⋮ The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs ⋮ An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\) ⋮ Half-integral packing of odd cycles through prescribed vertices ⋮ Packing cycles through prescribed 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

Cites Work

• Unnamed Item
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Packing cycles through prescribed vertices
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Packing cycles in undirected graphs
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Packing Directed Circuits through Prescribed Vertices Bounded Fractionally
• Approximation algorithms and hardness results for cycle packing problems
• On Independent Circuits Contained in a Graph
• Approximability of Packing Disjoint Cycles
• A new proof and generalizations of a theorem of Erdős and Pósa on graphs withoutk+1 independent circuits
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Disjoint cycles intersecting a set of vertices