Counting substructures I: color critical graphs

By Dhruv Mubayi. 2009

53 citations recorded by the source corpus.

Let F be a graph which contains an edge whose deletion reduces its chromatic number. We prove tight bounds on the number of copies of F in a graph with a prescribed number of vertices and edges. Our results extend those of Simonovits [8], who proved that there is one copy of F , and of Rademacher, Erd} os [1, 2] and Lov asz

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/6ba89da4fad7496a1107b09876f18ac130442b52