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 language | English (US) |
---|---|
Pages (from-to) | 193-196 |
Number of pages | 4 |
Journal | Journal of Graph Theory |
Volume | 35 |
Issue number | 3 |
DOIs | |
State | Published - Nov 2000 |
All Science Journal Classification (ASJC) codes
- Geometry and Topology
Keywords
- Critical graph
- Cycle
- Extremal