The order of monochromatic subgraphs with a given minimum degree (Q1408537)

Summary: Let \(G\) be a graph. For a given positive integer \(d\), let \(f_G(d)\) denote the largest integer \(t\) such that in every coloring of the edges of \(G\) with two colors there is a monochromatic subgraph with minimum degree at least \(d\) and order at least \(t\). Let \(f_G(d)=0\) in case there is a \(2\)-coloring of the edges of \(G\) with no such monochromatic subgraph. Let \(f(n,k,d)\) denote the minimum of \(f_G(d)\) where \(G\) ranges over all graphs with \(n\) vertices and minimum degree at least \(k\). In this paper we establish \(f(n,k,d)\) whenever \(k\) or \(n-k\) are fixed, and \(n\) is sufficiently large. We also consider the case where more than two colors are allowed.