Long cycles in critical graphs

Noga Alon, Michael Krivelevich, Paul Seymour

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

It is shown that any k-critical graph with n vertices contains a cycle of length at least 2√log(n-1)/log(k-2), improving a previous estimate of Kelly and Kelly obtained in 1954.

Original languageEnglish (US)
Pages (from-to)193-196
Number of pages4
JournalJournal of Graph Theory
Volume35
Issue number3
DOIs
StatePublished - Nov 2000

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Critical graph
  • Cycle
  • Extremal

Fingerprint Dive into the research topics of 'Long cycles in critical graphs'. Together they form a unique fingerprint.

Cite this