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

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.

Sources & referencesView supporting material

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.