Loading...
Please wait, while we are loading the content...
Similar Documents
Ramsey numbers for degree monotone paths
| Content Provider | arXiv |
|---|---|
| Author | Caro, Yair Yuster, Raphael Zarb, Christina |
| Date of Submission | 2015-03-26 |
| Abstract | A path $v_1,v_2,\ldots,v_m$ in a graph $G$ is $degree$-$monotone$ if $deg(v_1) \leq deg(v_2) \leq \cdots \leq deg(v_m)$ where $deg(v_i)$ is the degree of $v_i$ in $G$. Longest degree-monotone paths have been studied in several recent papers. Here we consider the Ramsey type problem for degree monotone paths. Denote by $M_k(m)$ the minimum number $M$ such that for all $n \geq M$, in any $k$-edge coloring of $K_n$ there is some $1\leq j \leq k$ such that the graph formed by the edges colored $j$ has a degree-monotone path of order $m$. We prove several nontrivial upper and lower bounds for $M_k(m)$. |
| Related Links | https://arxiv.org/pdf/1503.07891.pdf |
| arXiv | 1503.07891 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Mathematics - Combinatorics Mathematics Degree sequences Generalized Ramsey theory Paths and cycles |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics |
