Ramsey numbers for degree monotone paths

详细信息    查看全文

• 作者：Yair Caro^a ; Raphael Yuster^b ; Christina Zarb^c ; ^{christina.zarb@um.edu.mt}
• 关键词：Ramsey ; Degrees ; Paths
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：6 February 2017
• 年：2017
• 卷：340
• 期：2
• 页码：124-131
• 全文大小：529 K
• 卷排序：340

文摘

A path v1,v2,…,vmv1,v2,…,vm in a graph GG is degree-monotone   if deg(v1)≤deg(v2)≤⋯≤deg(vm)deg(v1)≤deg(v2)≤⋯≤deg(vm) where deg(vi)deg(vi) is the degree of vivi in GG. Longest degree-monotone paths have been studied in several recent papers. Here we consider the Ramsey type problem for degree monotone paths. Denote by Mk(m)Mk(m) the minimum number MM such that for all n≥Mn≥M, in any kk-edge coloring of KnKn there is some 1≤j≤k1≤j≤k such that the graph formed by the edges colored jj has a degree-monotone path of order mm. We prove several nontrivial upper and lower bounds for Mk(m)Mk(m).