pith. sign in

arxiv: 1706.05642 · v1 · pith:DXIRR5FSnew · submitted 2017-06-18 · 🧮 math.CO

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

classification 🧮 math.CO
keywords numbergraphchromaticepsiloneveryfreegraphssubgraphs
0
0 comments X
read the original 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 $\epsilon:=\epsilon(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-\epsilon)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.

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.