Bensmail–Renault conjecture on locally irregular colorings of oriented graphs

For a,b{+,}a,b\in\{+,-\}, a digraph is (a,b)(a,b)-locally irregular if, for every arc uvuv, da(u)db(v)d^a(u)\neq d^b(v); let lir(+,+)(D)\mathrm{lir}^{(+,+)}(D) be the minimum number of colors in an arc coloring whose color classes are (+,+)(+,+)-locally irregular. Bensmail–Renault conjecture. Every oriented graph DD satisfies

lir(+,+)(D)3.\mathrm{lir}^{(+,+)}(D)\leq 3.

The source reports that the conjecture is open, while a general upper bound of five is known for arbitrary digraphs and deciding whether the index is at most two is NP-complete.

Sources & referencesView supporting material

Primary source

Igor Grzelec, Alfréd Onderko and Mariusz Woźniak, “Weak and strong local irregularity of digraphs”, arXiv:2502.07933 (2025).

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.