On graphs with small Ramsey numbers (Q2746201)

A linear upper bound on the Ramsey number for all unbalanced bipartite graphs which have a bound on the degree of the vertices in the large part is proved. For a real number \(0 < \gamma < 1\), a positive integer \(d \geq 3\), and \(n\) a sufficiently large integer, it is shown that if \(G\) is a bipartite graph with parts of order \(n\) and \(n^\gamma\) respectively such that the degree of each vertex in the largest part is at most \(d\), then \(R(G) \leq cn\) for some positive constant \(c\). More generally, if \(G\) is a graph of order \(n\) such that the vertices of degree exceeding \(d\) is an independent set, then for every \(\varepsilon > 0\) there is a constant \(C\) such that \(R(G) \leq C|G|^{1 + \varepsilon}\).