The order of monochromatic subgraphs with a given minimum degree
The electronic journal of combinatorics, Tome 10 (2003)
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.
@article{10_37236_1725,
author = {Yair Caro and Raphael Yuster},
title = {The order of monochromatic subgraphs with a given minimum degree},
journal = {The electronic journal of combinatorics},
year = {2003},
volume = {10},
doi = {10.37236/1725},
zbl = {1023.05047},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1725/}
}
Yair Caro; Raphael Yuster. The order of monochromatic subgraphs with a given minimum degree. The electronic journal of combinatorics, Tome 10 (2003). doi: 10.37236/1725
Cité par Sources :