2002/12/30 by Yair Caro, Caro, Yair, Raphael Yuster +1
Computer Science · Mathematics · #05C15 #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C15 #msc:05C35
paper · pdf · doi:10.48550/arxiv.math/0212373
arxiv created 2002/12/30 · openalex publication_date 2002/12/30 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph. For a given positive integer d, let fG(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. For n > k > d let f(n,k,d) denote the minimum of fG(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.