Ramsey numbers of degenerate graphs

Abstract: 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) | g e 2^{d^{2} 2^{c r}}

has Ramsey number at most

2^{d 2^{c r}} | V (H) |

. This solves a conjecture of Burr and ErdH{o}s from 1973.

Recommendations

Cited in

(33)

This page was built for publication: Ramsey numbers of degenerate graphs