Premium
Linear Ramsey numbers of sparse graphs
Author(s) -
Shi Lingsheng
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20103
Subject(s) - combinatorics , mathematics , ramsey's theorem , clique sum , chordal graph , conjecture , indifference graph , pathwidth , discrete mathematics , 1 planar graph , dense graph , bounded function , graph , line graph , mathematical analysis
The Ramsey number R ( G 1 , G 2 ) of two graphs G 1 and G 2 is the least integer p so that either a graph G of order p contains a copy of G 1 or its complement G c contains a copy of G 2 . In 1973, Burr and Erdős offered a total of $25 for settling the conjecture that there is a constant c = c ( d ) so that R ( G , G )≤ c | V ( G )| for all d ‐degenerate graphs G , i.e., the Ramsey numbers grow linearly for d ‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory