Some results on irregular decomposition of graphs - Lintzmayer, Carla N.; Mota, Guilherme O.; Rocha, Lucas S. da; Sambinelli, Maycon (Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da Computação, 2023)
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.