Decomposing graphs into a constant number of locally irregular subgraphs

A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index chi'(irr)(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, Przybylo, and Wozniak conjectured that if G can be decomposed into locally irregular subgraphs, then chi'(irr)(G) <= 3. In support of this conjecture, Przybylo showed that chi'(irr)(G) <= 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'(irr)(G) <= 10. This is the first general constant upper bound on the irregular chromatic index of bipartite graphs. Combining this result with Przybylo's result, we show that chi'(irr)(G) <= 328 for every graph G which admits a decomposition into locally irregular subgraphs. Finally, we show that chi'(irr)(G) <= 2 for every 16-edge-connected bipartite graph G. (C) 2016 Elsevier Ltd. All rights reserved.