Induced subgraphs of graphs with large chromatic number. III. Long holes
We prove a 1985 conjecture of Gyárfás that for all k, ℓ, every graph with sufficiently large chromatic number contains either a clique of cardinality more than k or an induced cycle of length more than ℓ.
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Springer Berlin Heidelberg
2016
|