Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue (Q2288360): Difference between revisions

In graph theory, researchers are very often concerned with induced subgraphs of graphs with large chromatic number, and especially, which induced cycles must occur. In this work, the authors unify and substantially extend results from a number of previous papers. It is shown that for every positive number \(k\) every graph with large chromatic number contains either a large complete subgraph or induced cycles of lengths modulo \(k\). In view of this, two conjectures of Kalai and Meshulam from the 1990's connecting the chromatic number of a graph with the homology of its independence complex are proved.