The unique-counterexample conjecture for locally irregular edge colorings

A graph is locally irregular if the degrees of the end-vertices of every edge are distinct. An edge coloring is locally irregular if every color induces a locally irregular subgraph. A graph is colorable if it admits a locally irregular edge coloring. For a colorable connected graph GG, let χirr(G)\chi_{\rm irr}^{\prime}(G) be the smallest number of colors required by such a coloring, and let BB denote the bow-tie graph. The unique-counterexample conjecture. The bow-tie graph BB is the only colorable connected graph with

χirr(B)>3.\chi_{\rm irr}^{\prime}(B)>3.

The paper proves that BB is the only counterexample among cacti, while the proposed assertion for general connected graphs remains open.

Sources & referencesView supporting material

Primary source

Jelena Sedlar and Riste Škrekovski, “Local Irregularity Conjecture vs. cacti”, arXiv:2207.03941 (2022).

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.