The four-color bound for locally irregular edge colorings of colorable graphs

About 4 years old · traced to

All graphs in this paper are finite and simple. A graph is locally irregular if the degrees of the endpoints of every edge are distinct. A locally irregular edge coloring is an edge coloring in which every color class induces a locally irregular subgraph. A graph is colorable if it admits such a coloring, and for a colorable graph GG, let χirr⁡′(G)\chi_{\operatorname{irr}}^{\prime}(G) be the minimum number of colors in a locally irregular edge coloring.

Four-color bound. Every colorable connected graph GG satisfies

χirr⁡′(G)≤4.\chi_{\operatorname{irr}}^{\prime}(G)\leq 4.

This is presented as a weaker version of the refuted Local Irregularity Conjecture, motivated by the bow-tie graph, which requires four colors. The supplied text does not establish whether the four-color bound is proved or remains open.

References

Primary source

Jelena Sedlar and Riste Škrekovski, “A note on the locally irregular edge colorings of cacti”, arXiv:2207.03143 (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.