Covering odd cycles (Q1272187)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Covering odd cycles |
scientific article; zbMATH DE number 1226447
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Covering odd cycles |
scientific article; zbMATH DE number 1226447 |
Statements
Covering odd cycles (English)
0 references
24 November 1998
0 references
If, in a graph, the number of vertices is \(n\), the length of the shortest odd cycle is \(g\), then the odd circuits can be covered by \(O({n \over g}\log({n \over g}))\) vertices and can also be covered by \(O(n^2/g^2)\) edges. The results, which are optimal, sharpen former estimates of Bollobás, Erdős, Simonovits, and Szemerédi.
0 references
extremal graph theory
0 references
