A hole in a graph is an induced subgraph which is a cycle of length at least four. We prove that for all ν>0, every triangle-free graph with sufficiently large chromatic number contains holes of ν consecutive lengths.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Graph colouring
- Induced subgraphs