کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649735 1342465 2009 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An oriented coloring of planar graphs with girth at least five
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
An oriented coloring of planar graphs with girth at least five
چکیده انگلیسی

An oriented kk-coloring of an oriented graph GG is a homomorphism from GG to an oriented graph HH of order kk. We prove that every oriented graph with a maximum average degree less than 103 and girth at least 5 has an oriented chromatic number at most 16. This implies that every oriented planar graph with girth at least 5 has an oriented chromatic number at most 16, that improves the previous known bound of 19 due to Borodin et al. [O.V. Borodin, A.V. Kostochka, J. Nešetřil, A. Raspaud, É. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math. 206 (1999) 77–89].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 8, 28 April 2009, Pages 2108–2118
نویسندگان
,