stylistic:style_transfer, quality:corruption, stylistic:tone
Special cases

While the general bounds for the induced Ramsey numbers are exponential in the size of the graph, the behaviour is much different on special classes of graphs (in particular, sparse ones). Many of these classes have induced Ramsey numbers polynomial in the number of vertices.

If H is a cycle, path or star on k vertices, it is known that r (H) is linear in k.

If H is a tree on k vertices, it is known that r (H) = O (k log k). It is also known that r (H) is superlinear (i.e. r (H) = ω(k)). Note that this is in contrast to the usual Ramsey numbers, where the Burr–Erdős conjecture (now proven) tells us that r (H) is linear (since trees are 1- degenerate).

For graphs H with number of vertices k and bounded degree Δ, it was conjectured that r (H) ≤ cn, for some constant d depending only on Δ. This result was first proven by Łuczak and Rödl in 1996, with d (Δ) growing as a tower of twos with height O (Δ). More reasonable bounds for d (Δ) were obtained since then. In 2013, Conlon, Fox and Zhao showed using a counting lemma for sparse pseudorandom graphs that r (H) ≤ cn, where the exponent is best possible up to constant factors.