Covering odd cycles
type: Item
instance of: scholarly article
title: Covering odd cycles
zbMATH Open document ID: 0902.05036
DOI: 10.1007/BF01215920
published in: Combinatorica
publication date: 1998-11-24T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1226447
zbMATH Keywords: extremal graph theory
author: János Komlós
reviewed by: Péter Komjáth
MaRDI profile type: Publication
cites work: Ramanujan graphs
description: scientific article; zbMATH DE number 1226447