On two problems in graph Ramsey theory (Q377800)

It is proved that if \(G\) is a graph of order \(n\) and with maximum degree \(\Delta\), then the Ramsey number \(r(G) \leq c(\Delta)n\) with \(c(\Delta) \leq 2^{c\Delta\log \Delta}\). This improves the bound \(c(\Delta) \leq 2^{c\Delta\log^2 (\Delta)}\) proved by \textit{R. L. Graham} et al. in [J. Graph Theory 35, No. 3, 176--192 (2000; Zbl 0965.05073)]. The induced Ramsey number \(r_{\mathrm{ind}}(G)\) is the least positive integer \(n\) for which there exists a graph \(H\) on \(n\) vertices such that in any \(2\)-coloring of the edges of \(H\) there is a monochromatic induced copy of \(G\). It was conjectured by Erdős that there is a constant \(c\) such that \(r_{\mathrm{ind}}(G) \leq 2^{cn}\). The authors prove that \(r_{\mathrm{ind}}(G) \leq 2^{cn \log n}\), which improves on the previous best bound of \textit{Y. Kohayakawa} et al. in [Combinatorica 18, No. 3, 373-404 (1998; Zbl 0913.05074)]. They also prove the following result: There is a constant \(c\) such that for any positive integer \(n\) and any \((1/2,\lambda)\)-pseudo-random graph \(G\) on \(N\) vertices with \(\lambda \leq 2^{-cn \log n}N\), every graph on \(n\) vertices occurs as an induced monochromatic copy (in the same color) in all \(2\)-edge colorings of \(G\).