Ramsey numbers for degree monotone paths

Yair Caro; Raphael Yuster; Christina Zarb

paper

Ramsey numbers for degree monotone paths

arXiv:1503.07891

Abstract

A path $v_{1}, v_{2}, \dots, v_{m}$ in a graph $G$ is $d e g r ee$ - $m o n o t o n e$ if $d e g (v_{1}) \leq d e g (v_{2}) \leq \dots \leq d e g (v_{m})$ where $d e g (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)$ .

References in corpus (1)

Degree Monotone Paths