Authors
Citation
Ad. Scott, Induced cycles and chromatic number, J COMB TH B, 76(2), 1999, pp. 150-154
Citations number
8
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956
→ ACNP
Volume
76
Issue
2
Year of publication
1999
Pages
150 - 154
Database
ISI
SICI code
0095-8956(199907)76:2<150:ICACN>2.0.ZU;2-X
Abstract
We prove that, for any pair of integers k, l greater than or equal to 1, th
ere exists an integer N(k, l) such that every graph with chromatic number a
t least N(k, l) contains either K-k or an induced odd cycle of length at le
ast 5 or an induced cycle of length at least l. (C) 1999 Academic Press.