Recent techniques and results on the Erdős-Pósa property
From MaRDI portal
Publication:2403789
DOI10.1016/j.dam.2016.12.025zbMath1369.05177arXiv1603.04615OpenAlexW2962772870MaRDI QIDQ2403789
Jean-Florent Raymond, Dimitrios M. Thilikos
Publication date: 12 September 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1603.04615
girthtree decompositionsErdős-Pósa propertygraph minorsmin-max theoremstree partitionstopological minorsgraph immersions
Trees (05C05) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)
Related Items (17)
Packing cycles in undirected group-labelled graphs ⋮ On the Erd\H{o}s-P\'osa property for immersions and topological minors in tournaments ⋮ Towards a conjecture of Birmelé–Bondy–Reed on the Erdős–Pósa property of long cycles ⋮ Even A‐cycles 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 ⋮ A Tight Erdös--Pósa Function for Wheel Minors ⋮ Erdös--Pósa from Ball Packing ⋮ Packing \(A\)-paths of length zero modulo four ⋮ Packing and covering immersions in 4-edge-connected graphs ⋮ An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\) ⋮ Packing and Covering Induced Subdivisions ⋮ Erdös--Pósa Property for Labeled Minors: 2-Connected Minors ⋮ Graphs without two vertex-disjoint \(S\)-cycles ⋮ In absence of long chordless cycles, large tree-width becomes a local phenomenon ⋮ $K_4$-Subdivisions Have the Edge-Erdös--Pósa Property
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Edge-disjoint odd cycles in 4-edge-connected graphs
- An edge variant of the Erdős-Pósa property
- Approximate min-max relations on plane graphs
- The Erdős-Pósa property for clique minors in highly connected graphs
- The structure of graphs not admitting a fixed immersion
- A well-quasi-order for tournaments
- Packing cycles with modularity constraints
- Packing directed circuits exactly
- Disjoint cycles intersecting a set of vertices
- Tournament pathwidth and topological containment
- Tournament immersion and cutwidth
- Girth in graphs
- The Erdős-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces
- Packing non-zero \(A\)-paths in group-labelled graphs
- Maximum number of fixed points in regulatory Boolean networks
- Highly parity linked graphs
- The Erdös-Pósa property for matroid circuits
- Graph minors. V. Excluding a planar graph
- Mangoes and blueberries
- Tree-partitions of infinite graphs
- On two minimax theorems in graph
- Über die Maximalzahl kantendisjunkter A-Wege
- Über die Maximalzahl kreuzungsfreier H-Wege
- Packing and covering triangles in graphs
- Quickly excluding a planar graph
- Treewidth. Computations and approximations
- Transversals of \(d\)-intervals
- The Gallai-Younger conjecture for planar graphs
- Packing directed circuits
- Packing and covering triangles in tripartite graphs
- Piercing \(d\)-intervals
- Packing cycles in graphs
- Packing cycles in graphs. II
- Edge-disjoint odd cycles in planar graphs.
- Fixed points and maximal independent sets in AND-OR networks
- Covering a hypergraph of subgraphs
- Directed tree-width
- A short proof of Mader's \(\mathcal S\)-paths theorem
- On a conjecture of Tuza about packing and covering of triangles
- On tree-partitions of graphs
- Packing circuits in eulerian digraphs
- Packing and covering triangles in \(K_{4}\)-free planar graphs
- Small edge sets meeting all triangles of a graph
- Optimal packings of edge-disjoint odd cycles
- Half-integral packing of odd cycles through prescribed vertices
- Packing cycles through prescribed vertices
- A conjecture on triangles of graphs
- Fixed-parameter tractability for subset feedback set problems with parity constraints
- The Erdős-Pósa property for long circuits
- Non-zero disjoint cycles in highly connected group labelled graphs
- VC-dimension and Erdős-Pósa property
- An $$O(\log \mathrm{OPT})$$ O ( log OPT ) -Approximation for Covering/Packing Minor Models of $$\theta _{r}$$ θ r
- Quadratic Upper Bounds on the Erdős-Pósa Property for a Generalization of Packing and Covering Cycles
- A Tighter Erdős-Pósa Function for Long Cycles
- Strengthening Erdös-Pósa property for minor-closed graph classes
- Packing and Covering Immersion Models of Planar Subcubic Graphs
- Two disjoint negative cycles in a signed graph
- Approximate Min-max Relations for Odd Cycles in Planar Graphs
- On the presence of disjoint subgraphs of a specified type
- A Minimax Theorem for Directed Graphs
- Approximation and Kernelization for Chordal Vertex Deletion
- Packing Directed Circuits through Prescribed Vertices Bounded Fractionally
- (Meta) Kernelization
- Polynomial bounds for the grid-minor theorem
- On Independent Circuits Contained in a Graph
- Number of Fixed Points and Disjoint Cycles in Monotone Boolean Networks
- An exact characterization of tractable demand patterns for maximum disjoint path problems
- Excluded Forest Minors and the Erdős–Pósa Property
- Polynomial gap extensions of the Erdős-Pósa theorem
- Large-treewidth graph decompositions and applications
- Additivity of the genus of a graph
- A new proof and generalizations of a theorem of Erdős and Pósa on graphs withoutk+1 independent circuits
- Integer Programming and Combinatorial Optimization
- Packing directed cycles through a specified vertex set
- Ein Neuer Beweis Eines Mengerschen Satzes
- The Erdős-Pósa property for odd cycles in highly connected graphs
- The Erdős-Pósa property for odd cycles in graphs of large connectivity
This page was built for publication: Recent techniques and results on the Erdős-Pósa property
