Decomposing graphs into a constant number of locally irregular subgraphs

Abstract

A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index ${\chi }_{\mathrm{irr}}^{\prime }(G)$ of a graph $G$ is the smallest number of locally irregular subgraphs needed to edge-decompose $G$. Not all graphs have such a decomposition, but Baudon, Bensmail, Przybyło, and Woźniak conjectured that if $G$ can be decomposed into locally irregular subgraphs, then ${\chi }_{\mathrm{irr}}^{\prime }(G)\le 3$. In support of this conjecture, Przybyło showed that ${\chi }_{\mathrm{irr}}^{\prime }(G)\le 3$ holds whenever $G$ has minimum degree at least $10^{10}$. Here we prove that every bipartite graph $G$ which is not an odd length path satisfies ${\chi }_{\mathrm{irr}}^{\prime }(G)\le 10$. This is the first general constant upper bound on the irregular chromatic index of bipartite graphs. Combining this result with Przybyło's result, we show that ${\chi }_{\mathrm{irr}}^{\prime }(G)\le 328$ for every graph $G$ which admits a decomposition into locally irregular subgraphs. Finally, we show that ${\chi }_{\mathrm{irr}}^{\prime }(G)\le 2$ for every $16$-edge-connected bipartite graph $G$.