The Erdos-Posa theorem, named for Paul Erdos and Lajos Posa, relates two parameters of a graph: the largest number of vertex-disjoint cycles it contains, and the smallest size of a feedback vertex set, a set of vertices meeting every cycle. The theorem shows these two quantities are related by a function f(k), so a graph with no k vertex-disjoint cycles has a feedback vertex set bounded in terms of k, even though the gap between the two parameters can grow arbitrarily large in particular graphs.
Facts
Classification
Statement Form Erdos-Posa Theorem
Filter Results1 entry
Connections
Has Statement Form
In Branch
Source Erdos-Posa theorem (Wikipedia)
Principal Result Of
Source Erdos-Posa Theorem (Wikipedia)
Proved By
Source Erdos-Posa theorem (Wikipedia)
Sources
1. Erdos-Posa theorem (Wikipedia)
Lead section
In the mathematical discipline of graph theory, the Erdős-Pósa theorem, named after Paul Erdős and Lajos Pósa, relates two parameters of a graph: The size of the largest collection of vertex-disjoint cycles contained in the graph; The size of the smallest feedback vertex set in the graph: a set that contains one vertex from every cycle.
- In Branch: Graph Theory, Lead sentence
View the SourceErdos-Posa Theorem (Wikipedia)
Principal Result Of: Paul Erdos, Lead sentence of the article on the resultQuote, Principal Result Of: Paul Erdos, Lead sentence of the article on the result
In the mathematical discipline of graph theory, the Erdős-Pósa theorem, named after Paul Erdős and Lajos Pósa, relates two parameters of a graph: The size of the largest collection of vertex-disjoint cycles contained in the graph; The size of the smallest feedback vertex set in the graph: a set that contains one vertex from every cycle.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.