On graphs with small Ramsey numbers. II. (Q558242): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00493-004-0024-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2053063933 / rank | |||
Normal rank |
Latest revision as of 20:09, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On graphs with small Ramsey numbers. II. |
scientific article |
Statements
On graphs with small Ramsey numbers. II. (English)
0 references
5 July 2005
0 references
[For Part I see \textit{A. V. Kostochka} and \textit{V. Rödl}, J. Graph. Theory 37, 198--204 (2001; Zbl 0994.05094).] A graph \(G\) is \(d\)-degenerate if every subgraph of \(G\) has a vertex of degree at most \(d\). Burr and Erdős conjectured that the Ramsey number of a \(d\)-degenerate graph is linear, i.e., \(R(G,G)\leq c | V(G)| \), for some appropriate constant \(c=c(d)\). The authors prove the following statement in this spirit. If \(G_1\) and \(G_2\) are \(d\)-degenerate, then \(R(G_1,G_2)\leq cn\Delta (G_1)\), where \(c=c(d)\) and \(\Delta\) is the maximum degree of \(G_1\). An immediate corollary is that the Ramsey number of a \(d\)-degenerate graph is quadratic at most.
0 references
\(d\)-degenerate graphs
0 references
Burr-Erdős conjecture
0 references