Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5776870 | Discrete Mathematics | 2017 | 6 Pages |
Abstract
Consider a positive integer r and a graph G=(V,E) with maximum degree Î and without isolated edges. The least k so that a proper edge colouring c:Eâ{1,2,â¦,k} exists such that âeâuc(e)â âeâvc(e) for every pair of distinct vertices u,v at distance at most r in G is denoted by ÏΣ,râ²(G). For r=1, it has been proved that ÏΣ,1â²(G)=(1+o(1))Î. For any râ¥2 in turn an infinite family of graphs is known with ÏΣ,râ²(G)=Ω(Îrâ1). We prove that, on the other hand, ÏΣ,râ²(G)=O(Îrâ1) for râ¥2. In particular, we show that ÏΣ,râ²(G)â¤6Îrâ1 if râ¥4.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jakub PrzybyÅo,