Bensmail, Julien; Merker, Martin; Thomassen, Carsten Decomposing graphs into a constant number of locally irregular subgraphs. (English) Zbl 1348.05161 Eur. J. Comb. 60, 124-134 (2017). Summary: A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index \(\chi_{\operatorname{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 O. Baudon et al. [ibid. 49, 90–104 (2015; Zbl 1315.05105)] conjectured that if \(G\) can be decomposed into locally irregular subgraphs, then \(\chi_{\operatorname{irr}}^\prime(G) \leq 3\). In support of this conjecture, J. Przybyło [Electron. J. Comb. 23, No. 2, Research Paper P2.31, 13 p. (2016; Zbl 1338.05237)] showed that \(\chi_{\operatorname{irr}}^\prime(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_{\operatorname{irr}}^\prime(G) \leq 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_{\operatorname{irr}}^\prime(G) \leq 328\) for every graph \(G\) which admits a decomposition into locally irregular subgraphs. Finally, we show that \(\chi_{\operatorname{irr}}^\prime(G) \leq 2\) for every \(16\)-edge-connected bipartite graph \(G\). Cited in 1 ReviewCited in 18 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) Keywords:locally irregular graph; graph decomposition; edge set partition; 1-2-3 conjecture Citations:Zbl 1315.05105; Zbl 1338.05237 PDFBibTeX XMLCite \textit{J. Bensmail} et al., Eur. J. Comb. 60, 124--134 (2017; Zbl 1348.05161) Full Text: DOI arXiv References: [1] Baudon, O.; Bensmail, J.; Przybyło, J.; Woźniak, M., On decomposing regular graphs into locally irregular subgraphs, European J. Combin., 49, 90-104 (2015) · Zbl 1315.05105 [2] Baudon, O.; Bensmail, J.; Sopena, É., On the complexity of determining the irregular chromatic index of a graph, J. Discrete Algorithms, 30, 113-127 (2015) · Zbl 1320.05036 [3] Bensmail, J.; Stevens, B., Edge-partitioning graphs into regular and locally irregular components, Discrete Math. Theoret. Comput. Sci., 17, 3, 43-58 (2016) · Zbl 1336.05106 [4] Kalkowski, M.; Karoński, M.; Pfender, F., Vertex-coloring edge-weightings: towards the 1-2-3-conjecture, J. Combin. Theory Ser. B, 100, 3, 347-349 (2010) · Zbl 1209.05087 [5] Karoński, M.; Łuczak, T.; Thomason, A., Edge weights and vertex colours, J. Combin. Theory Ser. B, 91, 151-157 (2004) · Zbl 1042.05045 [6] Lovász, L. M.; Thomassen, C.; Wu, Y.; Zhang, C.-Q., Nowhere-zero 3-flows and modulo k-orientations, J. Combin. Theory Ser. B, 103, 587-598 (2013) · Zbl 1301.05154 [7] Przybyło, J., On decomposing graphs of large minimum degree into locally irregular subgraphs, Electron. J. Combin., 23, 2, #P2.31 (2016) · Zbl 1338.05237 [9] Thomassen, C., The weak 3-flow conjecture and the weak circular flow conjecture, J. Combin. Theory Ser. B, 102, 521-529 (2012) · Zbl 1239.05083 [10] Thomassen, C., Graph factors modulo \(k\), J. Combin. Theory Ser. B, 106, 174-177 (2014) · Zbl 1300.05262 [11] Thomassen, C.; Wu, Y.; Zhang, C.-Q., The 3-flow conjecture, factors modulo \(k\), and the 1-2-3-conjecture, J. Combin. Theory Ser. B, 121, 308-325 (2016) · Zbl 1348.05085 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.