Ramsey numbers of degenerate graphs

By Choongbum Lee. 2015

51 citations recorded by the source corpus.

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)| \ge 2^{d^22^{cr}}$ has Ramsey number at most $2^{d2^{cr}} |V(H)|$. This solves a conjecture of Burr and Erdős from 1973.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/e0b496a287de8480f2a5b175ab2bca19579433af