The rr-adjacent strong chromatic index conjecture

For a graph GG, two distinct vertices are rr-adjacent if their distance is at most rr. Let χa,r(G)\chi'_{a,r}(G) denote the least number of colours in a proper edge colouring of GG such that the sets of colours incident with any two rr-adjacent vertices are distinct. Write Δ(G)\Delta(G) and δ(G)\delta(G) for the maximum and minimum degrees of GG, respectively.

The rr-adjacent strong chromatic index conjecture. For each positive integer rr there exist constants δ0\delta_0 and CC such that

χa,r(G)Δ(G)+C\chi'_{a,r}(G)\leq \Delta(G)+C

for every graph without an isolated edge and with δ(G)δ0\delta(G)\geq\delta_0.

The conjecture proposes a uniform additive bound above the maximum degree when the minimum degree is sufficiently large. The source explains that the threshold δ0\delta_0 should be roughly equal to rr, up to a small additive constant, but does not state a resolution.

Sources & referencesView supporting material

Primary source

Jakub Przybyło, “Distant set distinguishing edge colourings of graphs”, arXiv:1508.05024 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.