کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903142 | 1632403 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A new approach to the chromatic number of the square of Kneser graph K(2k+1,k)
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The vertices of Kneser graph K(n,k) are the subsets of {1,2,â¦,n} of cardinality k, two vertices are adjacent if and only if they are disjoint. The square G2 of a graph G is defined on the vertex set of G with two vertices adjacent if their distance in G is at most 2. Z. Füredi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when n=2k+1. It is believed that Ï(K2(2k+1,k))=2k+c where c is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: 8kâ3+20â3 for 1kâ¥3 (Kim and Park, 2014) and 32kâ15+32 for kâ¥7 (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to Ï(K2(2k+1,k))â¤5kâ2+c, where c is a constant in {5â2,9â2,5,6}, depending on kâ¥2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 1, January 2018, Pages 96-103
Journal: Discrete Mathematics - Volume 341, Issue 1, January 2018, Pages 96-103
نویسندگان
Jeong-Hyun Kang,