pith. sign in

arxiv: 1408.2172 · v1 · pith:7YCVTH2Dnew · submitted 2014-08-10 · 💻 cs.DM · math.CO

Graphs with large chromatic number induce 3k-cycles

classification 💻 cs.DM math.CO
keywords chromaticlargenumbercyclesgraphgraphsquestionanswering
0
0 comments X
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.