2017/03/14 by Przybyło, Jakub
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1703.04815
For any graph G=(V,E) with maximum degree Δ and without isolated edges, and a positive integer r, by χ'Σ,r(G) we denote the r-distant sum distinguishing index of G. This is the least integer k for which a proper edge colouring c:E→\1,2,…,k\ exists such that ∑e\ni uc(e)≠ ∑e\ni vc(e) for every pair of distinct vertices u,v at distance at most r in G. It was conjectured that χ'Σ,r(G)≤ (1+o(1))Δr-1 for every r≥ 3. Thus far it has been in particular proved that χ'Σ,r(G)≤ 6Δr-1 if r≥ 4. Combining probabilistic and constructive approach, we show that this can be improved to χ'Σ,r(G)≤ (4+o(1))Δr-1 if the minimum degree of G equals at least ln8Δ.