Some results on irregular decomposition of graphs
A graph is locally irregular if any pair of adjacent vertices have distinct degrees. A locally irregular decomposition of a graph G is a decomposition of G into subgraphs that are locally irregular. We prove that any graph G can be decomposed into at most 2∆(G) − 1 locally irregular graphs, improving on the previous upper bound of 3∆(G)−2. We also show some results on subcubic and non-decomposable graphs.
Baudon, O., Bensmail, J., Przybyło, J., and Woźniak, M. (2015). On decomposing regular graphs into locally irregular subgraphs. European Journal of Combinatorics, 49:90–104.
Bensmail, J. (2020). A contribution to distinguishing labellings of graphs. Habilitation à diriger des recherches, Université côte d’azur.
Bensmail, J., Dross, F., and Nisse, N. (2020). Decomposing degenerate graphs into locally irregular subgraphs. Graphs and Combinatorics, 36:1869–1889.
Karoński, M., Łuczak, T., and Thomason, A. (2004). Edge weights and vertex colours. Journal of Combinatorial Theory Series B, 91(1):151–157.
Lei, H., Lian, X., Shi, Y., and Zhao, R. (2022). Graph classes with locally irregular chromatic index at most 4. Journal of Optimization Theory and Applications, pages 1–16.
Lintzmayer, C. N., Mota, G. O., and Sambinelli, M. (2021). Decomposing split graphs into locally irregular graphs. Discrete Applied Mathematics, 292:33–44.
Lužar, B., Przybyło, J., and Soták, R. (2018). New bounds for locally irregular chromatic index of bipartite and subcubic graphs. Journal of Combinatorial Optimization, 36(4):1425–1438.
Przybyło, J. (2015). On decomposing graphs of large minimum degree into locally irregular subgraphs. arXiv preprint arXiv:1508.01129.
Sedlar, J. and Škrekovski, R. (2021). Remarks on the local irregularity conjecture. Mathematics, 9(24).