On graphs with small Ramsey numbers. II.
type: Item
instance of: scholarly article
title: On graphs with small Ramsey numbers. II.
zbMATH Open document ID: 1063.05101
author: Alexandr Kostochka
author: Vojtěch Rödl
published in: Combinatorica
publication date: 2005-07-05T00:00:00Z
review text: [For Part I see \textit{A. V. Kostochka} and \textit{V. Rödl}, J. Graph. Theory 37, 198--204 (2001; Zbl 0994.05094).] A graph \(G\) is \(d\)-degenerate if every subgraph of \(G\) has a vertex of degree at most \(d\). Burr and Erdős conjectured that the Ramsey number of a \(d\)-degenerate graph is linear, i.e., \(R(G,G)\leq c | V(G)| \), for some appropriate constant \(c=c(d)\). The authors prove the following statement in this spirit. If \(G_1\) and \(G_2\) are \(d\)-degenerate, then \(R(G_1,G_2)\leq cn\Delta (G_1)\), where \(c=c(d)\) and \(\Delta\) is the maximum degree of \(G_1\). An immediate corollary is that the Ramsey number of a \(d\)-degenerate graph is quadratic at most.
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 2186324
zbMATH Keywords: \(d\)-degenerate graphs
zbMATH Keywords: Burr-Erdős conjecture
MaRDI profile type: Publication
full work available at URL: s00493-004-0024-9
OpenAlex ID: W2053063933
DOI: 10.1007/S00493-004-0024-9
description: scientific article; zbMATH DE number 2186324