Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes

Alex Scott, Paul Seymour

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)180-235
Number of pages56
JournalJournal of Combinatorial Theory. Series B
Volume132
DOIs
StatePublished - Sep 2018

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Graph colouring
  • Holes
  • Induced subgraphs
  • χ-boundedness

Fingerprint Dive into the research topics of 'Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes'. Together they form a unique fingerprint.

  • Cite this