|کد مقاله||کد نشریه||سال انتشار||مقاله انگلیسی||ترجمه فارسی||نسخه تمام متن|
|4646564||1413648||2017||8 صفحه PDF||ندارد||دانلود کنید|
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).
Journal: Discrete Mathematics - Volume 340, Issue 2, 6 February 2017, Pages 124–131