Sparse Ramsey graphs
type: Item
instance of: scholarly article
title: Sparse Ramsey graphs
zbMATH Open document ID: 0543.05048
DOI: 10.1007/BF02579159
author: Vojtěch Rödl
author: J. Nešetřil
published in: Combinatorica
publication date: 1984-01-01T00:00:00Z
review text: Let H be a graph which is the union of copies of a graph G. Associated with H (and the specified copies of G) is the hypergraph \({\mathcal H}\) whose vertices are the edges of H and whose hyperedges are the edge sets of these specified copies of G. The graph H t-arrows G \((H\to(G)_ t)\) if for any coloring of the edges of H with t colors, there is an induced copy of G in at least one of the colors. The following, which implies that there are very sparse Ramsey graphs for any graph G, is the main result. Theorem: For every pair of integers m, t and for any graph G there exists a graph H which is the union of copies of the graph G such that \(H\to(G)_ t\) and \({\mathcal H}\) does not contain any cycle of length less m. In the case when G is a complete graph, as well as for other special classes of graphs, the previous result is valid when the specified copies of G are all copies of G.
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 3863245
zbMATH Keywords: coloring of edges
zbMATH Keywords: induced copy
zbMATH Keywords: Ramsey graphs
MaRDI profile type: Publication
cites work: On chromatic number of graphs and set-systems
cites work: Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
cites work: On chromatic number of finite set-systems
cites work: The Ramsey property for graphs with forbidden complete subgraphs
cites work: A short proof of the existence of highly chromatic hypergraphs without short cycles
full work available at URL: https://doi.org/10.1007/bf02579159
OpenAlex ID: W2051667449
Recommended article: Ramsey numbers for sparse graphs
Recommended article: Sparse anti-Ramsey graphs
Recommended article: On Ramsey Numbers of Sparse Graphs
Recommended article: Ramsey numbers of sparse hypergraphs
Recommended article: Linear Ramsey numbers of sparse graphs
Recommended article: On globally sparse Ramsey graphs
Recommended article: Multipartite graph-sparse graph Ramsey numbers
Recommended article: Globally sparse vertex‐ramsey graphs
Recommended article: Q3337503
description: scientific article; zbMATH DE number 3863245