Induced Subgraphs of Graphs With Large Chromatic Number. X. Holes of Specific Residue

Alex Scott, Paul Seymour

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

A large body of research in graph theory concerns the induced subgraphs of graphs with large chromatic number, and especially which induced cycles must occur. In this paper, we unify and substantially extend results from a number of previous papers, showing that, for every positive integer k, every graph with large chromatic number contains either a large complete subgraph or induced cycles of all lengths modulo k. As an application, we prove two conjectures of Kalai and Meshulam from the 1990’s connecting the chromatic number of a graph with the homology of its independence complex.

Original languageEnglish (US)
Pages (from-to)1105-1132
Number of pages28
JournalCombinatorica
Volume39
Issue number5
DOIs
StatePublished - Nov 1 2019

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Induced Subgraphs of Graphs With Large Chromatic Number. X. Holes of Specific Residue'. Together they form a unique fingerprint.

  • Cite this