H-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups

Abstract: We consider the structure of

H

-free subgraphs of graphs with high minimal degree. We prove that for every

k > m

there exists an

e p s i l o n := e p s i l o n (k, m) > 0

so that the following holds. For every graph

H

with chromatic number

k

from which one can delete an edge and reduce the chromatic number, and for every graph

G

on

n > n_{0} (H)

vertices in which all degrees are at least

(1 - e p s i l o n) n

, any subgraph of

G

which is

H

-free and contains the maximum number of copies of the complete graph

K_{m}

is

(k - 1)

-colorable. We also consider several extensions for the case of a general forbidden graph

H

of a given chromatic number, and for subgraphs maximizing the number of copies of balanced blowups of complete graphs.

Recommendations

Cites Work

Cited In (4)

This page was built for publication: \(H\)-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups