On induced Ramsey numbers for graphs with bounded maximum degree (Q1924131)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On induced Ramsey numbers for graphs with bounded maximum degree |
scientific article |
Statements
On induced Ramsey numbers for graphs with bounded maximum degree (English)
0 references
26 January 1997
0 references
The induced Ramsey number \(r_{\text{ind}}(H)\) for a graph \(H\) is defined as the minimum number of vertices in a graph \(G\) which has the property that every 2-edge colouring of \(G\) yields an induced monochromatic copy of \(H\). It is shown that for every \(d\geq 1\) there exists an absolute constant \(c_d\) such that \(r_{\text{ind}}(H_{n, d})\leq n^{c_d}\) for every graph \(H_{n, d}\) with \(n\) vertices and the minimum degree at most \(d\). This confirms a conjecture suggested by W. T. Trotter.
0 references
Ramsey number
0 references