Article ID Journal Published Year Pages File Type
5776870 Discrete Mathematics 2017 6 Pages PDF
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
,