On Local Irregularity Conjecture for 2-multigraphs

Abstract

A multigraph in which adjacent vertices have different degrees is called locally irregular. The locally irregular edge coloring is an edge coloring of a multigraph $G$ in which every color induces a locally irregular submultigraph of $G$. We denote by $\mathrm{lir}(G)$ the locally irregular chromatic index of a multigraph $G$, which is the smallest number of colors required in a locally irregular edge coloring of $G$, given that such a coloring of $G$ exists. By ${}^{2}G$ we denote a 2-multigraph obtained from a simple graph $G$ by doubling each its edge. In 2022 Grzelec and Woźniak conjectured that $\mathrm{lir}{(}^{2}G)\le 2$ for every connected simple graph $G$ different from $K_2$; the conjecture is known as Local Irregularity Conjecture for 2-multigraphs. In this paper, we prove this conjecture in the case of regular graphs, split graphs, and some particular families of subcubic graphs. Moreover, we provide a constant upper bound on the locally irregular chromatic index of planar 2-multigraphs (except for ${}^2{K}_2$), and we obtain a better constant upper bound on $\mathrm{lir}{(}^{2}G)$ if $G$ is a simple subcubic graph different from $K_2$. In the proofs, special decompositions of graphs and the relation of Local Irregularity Conjecture to the well-known 1-2-3 Conjecture are utilized.

22 pages, 11 figures