کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649748 | 1342465 | 2009 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Nordhaus–Gaddum inequalities for the fractional and circular chromatic numbers
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Nordhaus–Gaddum inequalities for the fractional and circular chromatic numbers Nordhaus–Gaddum inequalities for the fractional and circular chromatic numbers](/preview/png/4649748.png)
چکیده انگلیسی
For a graph GG on nn vertices with chromatic number χ(G)χ(G), the Nordhaus–Gaddum inequalities state that ⌈2n⌉≤χ(G)+χ(G¯)≤n+1, and n≤χ(G)⋅χ(G¯)≤⌊(n+12)2⌋. Much analysis has been done to derive similar inequalities for other graph parameters, all of which are integer-valued. We determine here the optimal Nordhaus–Gaddum inequalities for the circular chromatic number and the fractional chromatic number, the first examples of Nordhaus–Gaddum inequalities where the graph parameters are rational-valued.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 8, 28 April 2009, Pages 2223–2232
Journal: Discrete Mathematics - Volume 309, Issue 8, 28 April 2009, Pages 2223–2232
نویسندگان
J.I. Brown, R. Hoshino,