Ramsey numbers of degenerate graphs

2015/05/18 by Lee, Choongbum · 4 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1505.04773

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

Cited by

• A linear upper bound for zero-sum Ramsey numbers of bounded degree graphs
• An Optimal Bound for Ramsey Goodness of Cycles
• Ramsey numbers of digraphs with local edge structure
• Ramsey numbers for 1-degenerate 3-graphs

Related

• Two remarks on the Burr-Erdos conjecture
• A conjecture of Erdős on graph Ramsey numbers
• Around a conjecture of ErdHos on graph Ramsey numbers
• On two problems in graph Ramsey theory
• Ramsey numbers for 1-degenerate 3-graphs