2017/05/11 by Alex Scott, Scott, Alex, Paul Seymour +1 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1705.04609
openalex publication_date 2017/05/11 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
A large body of research in graph theory concerns the induced subgraphs of\ngraphs with large chromatic number, and especially which induced cycles must\noccur. In this paper, we unify and substantially extend results from a number\nof previous papers, showing that, for every positive integer k, every graph\nwith large chromatic number contains either a large complete subgraph or\ninduced cycles of all lengths modulo k. As an application, we prove two\nconjectures of Kalai and Meshulam from the 1990's connecting the chromatic\nnumber of a graph with the homology of its independence complex.\n