Long cycles in critical graphs

Noga Alon; Michael Krivelevich; Paul Seymour

doi:10.1002/1097-0118(200011)35:3<193::AID-JGT4>3.0.CO;2-G

Long cycles in critical graphs

Noga Alon
, Michael Krivelevich
, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

5 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 language	English (US)
Pages (from-to)	193-196
Number of pages	4
Journal	Journal of Graph Theory
Volume	35
Issue number	3
DOIs	https://doi.org/10.1002/1097-0118(200011)35:3<193::AID-JGT4>3.0.CO;2-G
State	Published - Nov 2000

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

Critical graph
Cycle
Extremal

Access to Document

10.1002/1097-0118(200011)35:3<193::AID-JGT4>3.0.CO;2-G

Cite this

@article{f83924f31eff44f892b7cd32a3b54dbf,

title = "Long cycles in critical graphs",

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.",

keywords = "Critical graph, Cycle, Extremal",

author = "Noga Alon and Michael Krivelevich and Paul Seymour",

year = "2000",

month = nov,

doi = "10.1002/1097-0118(200011)35:3<193::AID-JGT4>3.0.CO;2-G",

language = "English (US)",

volume = "35",

pages = "193--196",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - Long cycles in critical graphs

AU - Alon, Noga

AU - Krivelevich, Michael

AU - Seymour, Paul

PY - 2000/11

Y1 - 2000/11

N2 - 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.

AB - 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.

KW - Critical graph

KW - Cycle

KW - Extremal

UR - https://www.scopus.com/pages/publications/0034368419

UR - https://www.scopus.com/pages/publications/0034368419#tab=citedBy

U2 - 10.1002/1097-0118(200011)35:3<193::AID-JGT4>3.0.CO;2-G

DO - 10.1002/1097-0118(200011)35:3<193::AID-JGT4>3.0.CO;2-G

M3 - Article

AN - SCOPUS:0034368419

SN - 0364-9024

VL - 35

SP - 193

EP - 196

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

Long cycles in critical graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this