Some results on irregular decomposition of graphs
Resumo
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.
Referências
Baudon, O., Bensmail, J., Davot, T., Hocquard, H., Przybyło, J., Senhaji, M., Sopena, E., and Woźniak, M. (2019). A general decomposition theory for the 1-2-3 Conjecture and locally irregular decompositions. Discrete Mathematics & Theoretical Computer Science, vol. 21 no. 1, ICGT 2018.
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).
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).
Publicado
06/08/2023
Como Citar
LINTZMAYER, Carla N.; MOTA, Guilherme O.; ROCHA, Lucas S. da; SAMBINELLI, Maycon.
Some results on irregular decomposition of graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 10-14.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230304.
