Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue

Author: 

Scott, A
Seymour, P

Publication Date: 

2 October 2019

Journal: 

Combinatorica

Last Updated: 

2020-04-03T12:30:06.85+01:00

DOI: 

10.1007/s00493-019-3804-y

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.

Symplectic id: 

949941

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article