Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Erdős–Pósa_theorem> ?p ?o. }
Showing items 1 to 10 of
10
with 100 items per page.
- Erdős–Pósa_theorem abstract "In the mathematical discipline of graph theory, the Erdős–Pósa theorem, named after Paul Erdős and Lajos Pósa, states that there is a function f(k) such for each positive integer k, every graph either contains k vertex-disjoint circuits or it has a feedback vertex set of f(k) vertices that intersects every circuit. Furthermore, f(k) = O(k log k) in the sense of Big O notation. Because of this theorem, circuits are said to have the Erdős–Pósa property.The theorem claims that for any finite number k there is an appropriate (least) value f(k), with the property that every graph with no k vertex-disjoint circuits all circuits can be covered by f(k) vertices. This generalized an unpublished result of Béla Bollobás, which states that f(2) = 3. Erdős & Pósa (1965) obtained the bounds c1k log k < f(k) < c2k log k for the general case. The result suggests that although there are infinitely many different graphs with no k disjoint circuits, they split into finitely many simply describable classes. For the case k = 2, Lovász (1965) gave a complete characterization. Voss (1969) proved f(3) = 6 and 9 ≤ f(4) ≤ 12.".
- Erdős–Pósa_theorem wikiPageID "22211457".
- Erdős–Pósa_theorem wikiPageRevisionID "569355565".
- Erdős–Pósa_theorem subject Category:Theorems_in_graph_theory.
- Erdős–Pósa_theorem comment "In the mathematical discipline of graph theory, the Erdős–Pósa theorem, named after Paul Erdős and Lajos Pósa, states that there is a function f(k) such for each positive integer k, every graph either contains k vertex-disjoint circuits or it has a feedback vertex set of f(k) vertices that intersects every circuit. Furthermore, f(k) = O(k log k) in the sense of Big O notation.".
- Erdős–Pósa_theorem label "Erdős–Pósa theorem".
- Erdős–Pósa_theorem sameAs Erd%C5%91s%E2%80%93P%C3%B3sa_theorem.
- Erdős–Pósa_theorem sameAs Q5385325.
- Erdős–Pósa_theorem sameAs Q5385325.
- Erdős–Pósa_theorem wasDerivedFrom Erdős–Pósa_theorem?oldid=569355565.