The -adjacent strong chromatic index conjecture
The -adjacent strong chromatic index conjecture
For a graph , two distinct vertices are -adjacent if their distance is at most . Let denote the least number of colours in a proper edge colouring of such that the sets of colours incident with any two -adjacent vertices are distinct. Write and for the maximum and minimum degrees of , respectively.
The -adjacent strong chromatic index conjecture. For each positive integer there exist constants and such that
for every graph without an isolated edge and with .
The conjecture proposes a uniform additive bound above the maximum degree when the minimum degree is sufficiently large. The source explains that the threshold should be roughly equal to , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.