Non-Ramsey graphs are \(c\log n\)-universal
type: Item
instance of: scholarly article
title: Non-Ramsey graphs are \(c\log n\)-universal
zbMATH Open document ID: 0934.05090
author: Hans Jürgen Prömel
author: Vojtěch Rödl
published in: Journal of Combinatorial Theory. Series A
publication date: 2000-04-09T00:00:00Z
review text: It is shown that all graphs that are non-Ramsey graphs are universal graphs. More specifically, it is shown that for any constant \(c_1 > 0\), there is a constant \(c_2 > 0\), such that if \(G\) is a graph on \(n\) vertices with neither \(G\) nor its complement \(\overline{G}\) containing a complete graph of order \(c_1 \log_2 n\), then \(G\) contains as induced subgraphs all graphs of order \(c_2 \log_2 n\).
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 1383697
zbMATH Keywords: Ramsey
zbMATH Keywords: universal graphs
reviewed by: Ralph Faudree
MaRDI profile type: Publication
full work available at URL: jcta.1999.2972
OpenAlex ID: W1985481988
cites work: Some remarks on the theory of graphs
cites work: Ramsey-type theorems
cites work: A partition calculus in set theory
cites work: Q5759552
cites work: On a Ramsey type theorem
cites work: Erdős and Rényi conjecture
DOI: 10.1006/JCTA.1999.2972
description: scientific article; zbMATH DE number 1383697