On induced Ramsey numbers for graphs with bounded maximum degree (Q1924131)

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.