Graphs with large chromatic number induce 3k-cycles
classification
💻 cs.DM
math.CO
keywords
chromaticlargenumbercyclesgraphgraphsquestionanswering
read the original 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 paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.