Decomposing graphs into a constant number of locally irregular subgraphs

Julien Bensmail, Martin Merker, Carsten Thomassen

Published 2016-04-01Version 1

A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index $\chi_{\rm 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, Przyby{\l}o, and Wo\'zniak conjectured that if $G$ can be decomposed into locally irregular subgraphs, then $\chi_{\rm irr}'(G)\leq 3$. In support of this conjecture, Przyby{\l}o showed that $\chi_{\rm irr}'(G)\leq 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_{\rm irr}'(G)\leq 10$. This is the first general constant upper bound on the irregular chromatic index of bipartite graphs. Combining this result with Przyby{\l}o's result, we show that $\chi_{\rm irr}'(G) \leq 328$ for every graph $G$ which admits a decomposition into locally irregular subgraphs. Finally, we show that $\chi_{\rm irr}'(G)\leq 2$ for every $16$-edge-connected bipartite graph $G$.