A Kruskal-Katona Type Theorem for Graphs

Abstract

A bound on consecutive clique numbers of graphs is established. This bound is evaluated and shown to often be much better than the bound of the Kruskal-Katona theorem. A bound on non-consecutive clique numbers is also proven.

23 pages

References in corpus (1)

• Kruskal--Katona type theorems for clique complexes arising from chordal and strongly chordal graphs