کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648112 | 1342393 | 2012 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Two results on the digraph chromatic number
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
It is known (Bollobás (1978) [4]; Kostochka and Mazurova (1977) [12]) that there exist graphs of maximum degree ΔΔ and of arbitrarily large girth whose chromatic number is at least cΔ/logΔcΔ/logΔ. We show an analogous result for digraphs where the chromatic number of a digraph DD is defined as the minimum integer kk so that V(D)V(D) can be partitioned into kk acyclic sets, and the girth is the length of the shortest cycle in the corresponding undirected graph. It is also shown, in the same vein as an old result of Erdős (1962) [5], that there are digraphs with arbitrarily large chromatic number where every large subset of vertices is 2-colorable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 10, 28 May 2012, Pages 1823–1826
Journal: Discrete Mathematics - Volume 312, Issue 10, 28 May 2012, Pages 1823–1826
نویسندگان
Ararat Harutyunyan, Bojan Mohar,