کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903535 | 1632742 | 2019 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Acyclic subgraphs with high chromatic number
ترجمه فارسی عنوان
زیرگرافهای آسیکل با تعداد رنگ کروماتیک بالا
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
For an oriented graph G, let f(G) denote the maximum chromatic number of an acyclic subgraph of G. Let f(n) be the smallest integer such that every oriented graph G with chromatic number larger than f(n) has f(G)>n. Let g(n) be the smallest integer such that every tournament G with more than g(n) vertices has f(G)>n. It is straightforward that Ω(n)â¤g(n)â¤f(n)â¤n2. This paper provides the first nontrivial lower and upper bounds for g(n). In particular, it is proved that 14n8â7â¤g(n)â¤n2â(2â12)n+2. It is also shown that f(2)=3, i.e. every orientation of a 4-chromatic graph has a 3-chromatic acyclic subgraph. Finally, it is shown that a random tournament G with n vertices has f(G)=Î(nlogn) whp.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 75, January 2019, Pages 11-18
Journal: European Journal of Combinatorics - Volume 75, January 2019, Pages 11-18
نویسندگان
Safwat Nassar, Raphael Yuster,