کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649140 1632435 2010 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Coloring the square of the Cartesian product of two cycles
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Coloring the square of the Cartesian product of two cycles
چکیده انگلیسی

The square G2G2 of a graph GG is defined on the vertex set of GG in such a way that distinct vertices with distance at most 2 in GG are joined by an edge. We study the chromatic number of the square of the Cartesian product Cm□CnCm□Cn of two cycles and show that the value of this parameter is at most 7 except when (m,n)(m,n) is (3,3)(3,3), in which case the value is 9, and when (m,n)(m,n) is (4,4)(4,4) or (3,5)(3,5), in which case the value is 8. Moreover, we conjecture that whenever G=Cm□CnG=Cm□Cn, the chromatic number of G2G2 equals ⌈mn/α(G2)⌉⌈mn/α(G2)⌉, where α(G2)α(G2) denotes the maximum size of an independent set in G2G2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issues 17–18, 28 September 2010, Pages 2327–2333
نویسندگان
, ,