Ks-Free Graphs Without Large Kr-Free Subgraphs

DOI10.1017/S0963548300001243MaRDI QIDQ4314152zbMATH OpenOpenAlexFDO

Authors Michael Krivelevich

Publication date 9 April 1995

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548300001243

zbMATH Keywords

exponential correlation inequalityLovász Local Lemmaupper bound

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• Large K_r‐free subgraphs in K_s‐free graphs and some other Ramsey‐type problems
• \(K_4\)-free graphs without large induced triangle-free subgraphs
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers
• On the maximal number of certain subgraphs in \(K_ r\)-free graphs
• LARGE -FREE SUBGRAPHS IN -CHROMATIC GRAPHS
• On subgraphs of \(C_{2k}\)-free graphs
• Subgraphs in vertex neighborhoods ofKr-free graphs
• Extremal G-free induced subgraphs of Kneser graphs
• Subgraph densities in \(K_r\)-free graphs

Cites work

• Graphs without large triangle free subgraphs
• Local and global clique numbers
• Local constraints ensuring small representing sets
• Minimum number of elements of representing a set system of given rank
• On Turan's theorem for sparse graphs
• The Construction of Certain Graphs

Cited in

(23)

• On the minimal number of edges in color-critical graphs
• Constructive bounds for a Ramsey-type problem
• \(K_4\)-free graphs without large induced triangle-free subgraphs
• \(K_4\)-free subgraphs of random graphs revisited
• A new lower bound for a Ramsey-type problem
• Subgraph densities in \(K_r\)-free graphs
• On the minimum degree of minimal Ramsey graphs for multiple colours
• On the Ramsey-Turán number with small s-independence number
• On generalized Ramsey numbers of Erdős and Rogers
• Large K_r‐free subgraphs in K_s‐free graphs and some other Ramsey‐type problems
• Bounding Ramsey numbers through large deviation inequalities
• On the stability of the graph independence number
• Improved bounds for the Erdős-Rogers function
• Short proofs of some extremal results
• On generalized Ramsey numbers for 3-uniform hypergraphs
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
• On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
• Induced subgraphs of K_r-free graphs and the Erdős-Rogers problem
• Improved bounds for the Erdős-Rogers (s, s+2)-problem
• On the maximum F-free induced subgraphs in K_t-free graphs
• On the order of the classical Erdős-Rogers functions
• An almost quadratic bound on vertex Folkman numbers

This page was built for publication: K^s-Free Graphs Without Large K^r-Free Subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4314152)