All Title Author
Keywords Abstract

Mathematics  2014 

Graph colouring and the total Betti number

Full-Text   Cite this paper   Add to My Lib

Abstract:

The total Betti number of the independence complex of a graph is an intriguing graph invariant. Kalai and Meshulam have raised the question on its relation to cycles and the chromatic number of a graph, and a recent conjecture on that theme was proved by Bonamy, Charbit and Thomasse. We show an upper bound on the total Betti number in terms of the number of vertex disjoint cycles in a graph. The main technique is discrete Morse theory and building poset maps. Ramanujan graphs with arbitrary chromatic number and girth log(n) is a classical construction. We show that any subgraph of them with less than n^0.003 vertices have smaller total Betti number than some planar graph of the same order, although it is part of a graph with high chromatic number.

Full-Text

comments powered by Disqus

Contact Us

service@oalib.com

QQ:3279437679

微信:OALib Journal