arXiv Analytics

Sign in

arXiv:math/0212373 [math.CO]AbstractReferencesReviewsResources

The order of monochromatic subgraphs with a given minimum degree

Yair Caro, Raphael Yuster

Published 2002-12-30Version 1

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.

Related articles: Most relevant | Search more
arXiv:0707.2760 [math.CO] (Published 2007-07-18)
Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
arXiv:math/0605189 [math.CO] (Published 2006-05-08)
Perfect packings with complete graphs minus an edge
arXiv:1206.1376 [math.CO] (Published 2012-06-07, updated 2013-04-25)
Towards a weighted version of the Hajnal-Szemerédi Theorem