کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903632 1632748 2018 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Distant set distinguishing edge colourings of graphs
ترجمه فارسی عنوان
مجموعه ای از رنگ های متمایز از لبه های گراف را مشخص می کند
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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
نویسندگان
,