The order of monochromatic subgraphs with a given minimum degree
| dc.creator | Caro, Yair | |
| dc.creator | Yuster, Raphael | |
| dc.date | 2002-12-30 | |
| dc.date.accessioned | 2026-07-07T04:54:07Z | |
| dc.date.available | 2026-07-07T04:54:07Z | |
| dc.description | 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$. For $n > k > d$ 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. | |
| dc.identifier | https://arxiv.org/abs/math/0212373 | |
| dc.identifier | http://arxiv.org/abs/math/0212373 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/66120 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15; 05C35 | |
| dc.title | The order of monochromatic subgraphs with a given minimum degree | |
| dc.type | text |