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 , let be the smallest number of colors required by such a coloring, and let denote the bow-tie graph. The unique-counterexample conjecture. The bow-tie graph is the only colorable connected graph with
The paper proves that 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
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.