The four-color bound 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 graph GG, let χirr(G)\chi_{\rm irr}^{\prime}(G) be the smallest number of colors required by such a coloring. The four-color bound. Every colorable connected graph GG satisfies

χirr(G)4.\chi_{\rm irr}^{\prime}(G)\leq 4.

This weaker version of the Local Irregularity Conjecture is established for all colorable cacti, as stated in the paper’s context, so the candidate is treated as solved.

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.