کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651928 1632582 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Ramsey numbers of ordered graphs
ترجمه فارسی عنوان
تعداد رمزی از نمودارهای مرتب شده
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

An ordered graph is a graph together with a total ordering of its vertices. We study ordered Ramsey numbers, the analogue of Ramsey numbers for ordered graphs.In contrast with the case of unordered graphs, we show that there are ordered matchings whose ordered Ramsey numbers are super-polynomial in the number of vertices.We also prove that ordered Ramsey numbers are polynomial in the number of vertices of the given ordered graph G if G has constant degeneracy and constant interval chromatic number or if G has constant bandwidth. The latter result answers positively a question of Conlon, Fox, Lee, and Sudakov.For a few special classes of ordered graphs, we give asymptotically tight bounds for their ordered Ramsey numbers. For so-called monotone cycles we compute their ordered Ramsey numbers exactly.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 419-424