Degree Conditions for the Existence of Vertex-Disjoint Cycles and Paths: A Survey |
SpringerLink Skip to main content Advertisement SpringerLink Log in Menu Find a journal …

In the Subset Feedback Vertex Set (Subset FVS) problem, the input is a graph G on n
vertices and m edges, a subset of vertices T, referred to as terminals, and an integer k. The …

Several min–max relations in graph theory can be expressed in the framework of the Erdős–
Pósa property. Typically, this property reveals a connection between packing and covering …

The well-known theorem of Erdős and Pósa says that a graph G has either k vertex-disjoint
cycles or a vertex set X of order at most f (k) such that G∖ X is a forest. Starting with this …

Abstract A (Γ 1, Γ 2)-labeled graph is an oriented graph with its edges labeled by elements
of the direct sum of two groups Γ 1, Γ 2. A cycle in such a labeled graph is (Γ 1, Γ 2)-non-zero …

Abstract In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph
D and an integer k. The objective is to determine whether there exists a set of at most k …

A chordless cycle, or equivalently a hole, in a graph G is an induced subgraph of G which is
a cycle of length at least 4. We prove that the Erdős-Pósa property holds for chordless …

Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function
f: ℕ→ ℝ such that for all k∊ ℕ and all graphs G, either G contains k vertex-disjoint subgraphs …

The well-known Erdős-Pósa theorem says that for any integer k and any graph G, either G
contains k vertex-disjoint cycles or a vertex set X of order at most c· k log k (for some …

The Cycle Packing problem asks whether a given undirected graph G=(V,E) contains k
vertex-disjoint cycles. Since the publication of the classic Erdös--Pósa theorem in 1965 …