کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646638 | 1342309 | 2016 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The square chromatic number of the torus
ترجمه فارسی عنوان
عدد رنگی مربع از چنبره
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ آمیزی فاصله 2 ؛ ضرب دکارتی؛ توروس
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The square of a graph GG denoted by G2G2, is the graph with the same vertex set as GG and edges linking pairs of vertices at distance at most 2 in GG. The chromatic number of the square of the Cartesian product of two cycles was previously determined for some cases. In this paper, we determine the precise value of χ((Cm□Cn)2)χ((Cm□Cn)2) for all the remaining cases. We show that for all ordered pairs (m,n)(m,n) except for (7,11)(7,11) we have χ((Cm□Cn)2)=⌈|V((Cm□Cn)2)|α((Cm□Cn)2)⌉, where α(G)α(G) denotes the independent number of GG. This settles a conjecture of Sopena and Wu (2010). We also show that the smallest integer kk such that χ((Cm□Cn)2)≤6χ((Cm□Cn)2)≤6 for every m,n≥km,n≥k is 10. This answers a question of Shao and Vesel (2013).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 447–456
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 447–456
نویسندگان
A.G. Chegini, Morteza Hasanvand, E.S. Mahmoodian, Farokhlagha Moazami,