Note on a Ramsey-Turán type problem
type: Item
instance of: scholarly article
title: Note on a Ramsey-Turán type problem
zbMATH Open document ID: 0589.05043
DOI: 10.1007/BF02582954
author: Vojtěch Rödl
published in: Graphs and Combinatorics
publication date: 1985-01-01T00:00:00Z
review text: Let f(n,k,\(\ell)\) be the maximal integer m such that there is a graph on n vertices with m edges, clique number \(<k\), and independence number \(<\ell\). \textit{B. Bollobás} and \textit{P. Erdős} [J. Comb. Theory, Ser. B 21, 166-168 (1976; Zbl 0337.05134)] and independently \textit{E. Szemeredi} [Mat. Lapok 23 (1972), 113-116 (1973; Zbl 0277.05134)] proved that if \(\ell =o(n)\), then \(f(n,4,1\ell)=(1+o(1))n^ 2/8\). Erdős asked the question whether any such graph must contain a K(r,r,r). The author shows that this is not true by proving the existence of a graph with the above properties such that any subgraph on \(\ell\) vertices is the union of a bipartite graph and a forest. Thus, the graph does not have a K(3,3,3).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 3946170
zbMATH Keywords: chromatic number
zbMATH Keywords: clique number
zbMATH Keywords: independence number
MaRDI profile type: Publication
cites work: On a Ramsey-Turán type problem
cites work: Graph Theory and Probability
cites work: Q4401979
full work available at URL: https://doi.org/10.1007/bf02582954
OpenAlex ID: W1975359506
description: scientific article; zbMATH DE number 3946170