On Ramsey remainders for monochromatic induced subgraphs

Abstract

Let F and G be graphs. We define r* (F, G) as the smallest integer t such that all but at most t vertices of F can be partitioned into vertex-disjoint monochromatic induced copies of G for any 2-edge-coloring of F. Let r* (n, G) denote min r* (F, G) over all graphs F with no less than n vertices. We show that every graph G has a constant 0 ≤ c < 1 such that r* (n, G) ≤ n^c holds for sufficiently large n. It is not difficult to see that if G is a complete graph or a complete bipartite graph then Lim_n→∞ r* (n, G) < ∞. We show that if G is one of the following graphs, then r* (n, G) also converges: a graph with an isolated vertex, a complete bipartite graph minus one edge, or a star forest.