کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
11017682 1722376 2019 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Induced subgraphs of graphs with large chromatic number. XI. Orientations
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Induced subgraphs of graphs with large chromatic number. XI. Orientations
چکیده انگلیسی
Fix an oriented graph H, and let G be a graph with bounded clique number and very large chromatic number. If we somehow orient its edges, must there be an induced subdigraph isomorphic to H? Kierstead and Rödl (1996) raised this question for two specific kinds of digraph H: the three-edge path, with the first and last edges both directed towards the interior; and stars (with many edges directed out and many directed in). Aboulker et al. (2018) subsequently conjectured that the answer is affirmative in both cases. We give affirmative answers to both questions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 76, February 2019, Pages 53-61
نویسندگان
, , ,