کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903632 | 1632748 | 2018 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Distant set distinguishing edge colourings of graphs
ترجمه فارسی عنوان
مجموعه ای از رنگ های متمایز از لبه های گراف را مشخص می کند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We consider the following extension of the concept of adjacent strong edge colourings of graphs without isolated edges. Two distinct vertices which are at distance at most r in a graph are called r-adjacent. The least number of colours in a proper edge colouring of a graph G such that the sets of colours met by any r-adjacent vertices in G are distinct is called the r-adjacent strong chromatic index of G and denoted by Ïa,râ²(G). It has been conjectured that Ïa,1â²(G)â¤Î+2 if G is connected of maximum degree Îâ¥2 and non-isomorphic to C5, while Hatami proved that there is a constant C, Câ¤300, such that Ïa,1â²(G)â¤Î+C if Î>1020 [J. Combin. Theory Ser. B 95 (2005) 246-256]. We conjecture that a similar statement should hold for any r, i.e., that for each positive integer r there exist constants δ0 and C such that Ïa,râ²(G)â¤Î+C for every graph without an isolated edge and with minimum degree δâ¥Î´0, and argue that a lower bound on δ is unavoidable in such a case (for r>2). Using the probabilistic method we prove such an upper bound to hold for graphs with δâ¥ÏµÎ, for every r and any fixed εâ(0,1], i.e., in particular for regular graphs. We also support the conjecture by proving an upper bound Ïa,râ²(G)â¤(1+o(1))Î for graphs with δâ¥r+2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 69, March 2018, Pages 185-199
Journal: European Journal of Combinatorics - Volume 69, March 2018, Pages 185-199
نویسندگان
Jakub PrzybyÅo,