Graphs without large triangle free subgraphs

DOI10.1016/0012-365X(91)90042-ZMaRDI QIDQ1174161zbMATH OpenOpenAlexFDO

Authors S. Singh

Publication date 25 June 1992

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(91)90042-z

zbMATH Keywords

clique numberrandom graphstriangle free subgraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

Review text

The authors extend results of \textit{P. Erdős} and \textit{C. A. Rogers} [Can. J. Math. 14, 702--707 (1962; Zbl 0194.25304)]. They show that for \(2\leq r<s\) and large enough \(n\), there exist graphs on \(n\) vertices and clique number less than \(s\) in which every set of vertices, which is not too small, spans a clique on \(r\) vertices. Use is made of the theory of random graphs.

Recommendations

• Large triangle-free subgraphs in graphs without \(K_ 4\)
• On the edge distribution in triangle-free graphs
• The typical structure of graphs with no large cliques
• Triangle-free subgraphs of random graphs

Cites work

• Graph Theory and Probability
• Graph Theory and Probability. II
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3711961 (Why is no real title available?)
• scientific article; zbMATH DE number 3637904 (Why is no real title available?)
• The Construction of Certain Graphs

Cited in

(29)

• Large triangle-free subgraphs in graphs without \(K_ 4\)
• On the minimal number of edges in color-critical graphs
• Constructive bounds for a Ramsey-type problem
• Graphs without theta subgraphs
• On the edge distribution in triangle-free graphs
• \(K_4\)-free graphs without large induced triangle-free subgraphs
• Some induced subgraphs of strongly regular graphs with no triangles
• On the minimum degree of minimal Ramsey graphs for multiple colours
• On Triangle-Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph
• Each 11-vertex graph without 4-cliques has a triangle-free 2-partition of vertices
• On the Ramsey-Turán number with small s-independence number
• scientific article; zbMATH DE number 4139791 (Why is no real title available?)
• Extremal Graphs without Large Forbidden Subgraphs
• scientific article; zbMATH DE number 493467 (Why is no real title available?)
• Local-Global Phenomena in Graphs
• K^s-Free Graphs Without Large K^r-Free Subgraphs
• Triangle-Free Graphs with Large Degree
• On generalized Ramsey numbers of Erdős and Rogers
• On the stability of the graph independence number
• On the number of graphs without large cliques
• When does the \(K_{4}\)-free process stop?
• On generalized Ramsey numbers for 3-uniform hypergraphs
• On vertex Ramsey graphs with forbidden subgraphs
• No dense subgraphs appear in the triangle-free graph process
• On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers
• 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
• An almost quadratic bound on vertex Folkman numbers

This page was built for publication: Graphs without large triangle free subgraphs

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