Graphs with large chromatic number induce 3k-cycles

MaRDI QIDQ6253803zbMATH OpenFDO

Authors Marthe Bonamy, Pierre Charbit, Stéphan Thomassé

Publication date 9 August 2014

Abstract: Answering a question of Kalai and Meshulam, we prove that graphs without induced cycles of length $3k$ have bounded chromatic number. This implies the very first case of a much broader question asserting that every graph with large chromatic number induces a graph $H$ such that the sum of the Betti numbers of the independence complex of $H$ is also large.

This page was built for publication: Graphs with large chromatic number induce $3k$-cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6253803)