Ramsey numbers of degenerate graph

• 成果类型: Article
• 署名作者: Lee, Choongbum
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2017.185.3.2
• 发表日期: 2017
• 页码: 791-829
• 关键词: bipartite graphs

摘要

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(d22cr) has Ramsey number at most 2(d22cr) |V(H)|. This solves a conjecture of Burr and Erdos from 1973.