کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650593 | 1342494 | 2008 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Distance graphs with maximum chromatic number
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Distance graphs with maximum chromatic number Distance graphs with maximum chromatic number](/preview/png/4650593.png)
چکیده انگلیسی
The distance graph G(D)G(D) has the set of integers as vertices and two vertices are adjacent in G(D)G(D) if their difference is contained in the set D⊂ZD⊂Z. A conjecture of Zhu states that if the chromatic number of G(D)G(D) achieves its maximum value |D|+1|D|+1 then the graph has a triangle. The conjecture is proven to be true if |D|⩽3|D|⩽3. We prove that the chromatic number of a distance graph with D={a,b,c,d}D={a,b,c,d} is five only if either D={1,2,3,4k}D={1,2,3,4k} or D={a,b,a+b,b-a}D={a,b,a+b,b-a}. This confirms a stronger version of Zhu's conjecture for |D|=4|D|=4, namely, if the chromatic number achieves its maximum value then the graph contains K4K4.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 8, 28 April 2008, Pages 1355–1365
Journal: Discrete Mathematics - Volume 308, Issue 8, 28 April 2008, Pages 1355–1365
نویسندگان
Javier Barajas, Oriol Serra,