Ramsey numbers of degenerate graphs. (English) Zbl 1365.05193

Summary: A graph is \(d\)-degenerate if all its subgraphs have a vertex of degree at most \(d\). We prove that there exists a constant \(c\) such that for all natural numbers \(d\) and \(r\), every \(d\)-degenerate graph \(H\) of chromatic number \(r\) with \(|V(H)|\geq 2^{{d^2}2^{cr}}\) has Ramsey number at most \(2^{d2^{cr}}|V(H)|\). This solves a conjecture of S. A. Burr and P. Erdős [Colloq. Math. Soc. János Bolyai 10, 215–240 (1975; Zbl 0316.05110)].


05C55 Generalized Ramsey theory
05D10 Ramsey theory
05C07 Vertex degrees


Zbl 0316.05110
Full Text: DOI arXiv