The unique-counterexample conjecture for locally irregular edge colorings

At least 3 years old · documented by

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.

References

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.