Premium
Long cycles in critical graphs
Author(s) -
Alon Noga,
Krivelevich Michael,
Seymour Paul
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/1097-0118(200011)35:3<193::aid-jgt4>3.0.co;2-g
Subject(s) - mathematics , combinatorics , graph , discrete mathematics , graph theory
It is shown that any k ‐critical graph with n vertices contains a cycle of length at least $2\sqrt{log(n-1)/log(k-2)}$ , improving a previous estimate of Kelly and Kelly obtained in 1954. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 193–196, 2000