Abstract
A graph G is said to be locally irregular if each pair of adjacent vertices have different degrees in G. A collection of edge disjoint subgraphs \((G_1,\ldots ,G_k)\) of G is called a k-locally irregular decomposition of G if \((E(G_1),\ldots ,E(G_k))\) is an edge partition of G and each \(G_i\) is locally irregular for \(i\in \{1,\ldots ,k\}\). The locally irregular chromatic index of G, denoted by \(\chi '_{irr}(G)\), is the smallest integer k such that G can be decomposed into k locally irregular subgraphs. A graph G is said to be decomposable if \(\chi '_{irr}(G)\) is finite, otherwise, G is exceptional. The Local Irregularity Conjecture states that all connected graphs admit a 3-locally irregular decomposition except for odd paths, odd cycles, and a certain subclass of cacti. Recently, Sedlar and Škrekovski showed that there exists a graph G which is a cactus such that \(\chi '_{irr}(G)=4\). In this paper, we mainly prove that if G is a decomposable cactus, then \(\chi '_{irr}(G)\le 4\); if G is a decomposable cactus without nontrivial cut edges, then \(\chi '_{irr}(G)\le 3\). In addition, we show that in a decomposable subcubic graph G if each vertex of degree 3 lies on a triangle, then \(\chi '_{irr}(G)\le 3\). By establishing algorithms, we obtain \(\chi '_{irr}(K_n-C_\ell )\le 3\) for \(3\le \ell \le n-1\).





Similar content being viewed by others
References
Baudon, O., Bensmail, J., Przybyło, J., Woźniak, M.: On decomposing regular graphs into locally irregular subgraphs. Eur. J. Combin. 49, 90–104 (2015)
Bensmail, J., Dross, F., Nisse, N.: Decomposing degenerate graphs into locally irregular subgraphs. Graphs Comb. 36, 1869–1889 (2020)
Bensmail, J., Merker, M., Thomassen, C.: Decomposing graphs into a constant number of locally irregular subgraphs. Eur. J. Comb. 60, 124–134 (2017)
Bensmail, J., Renault, G.: Decomposing oriented graphs into six locally irregular oriented graphs. Graphs Comb. 32, 1707–1721 (2016)
Bensmail, J., Stevens, B.: Edge-partitioning graphs into regular and locally irregular components. Discrete Math. Theor. Comput. Sci. 17, 43–58 (2016)
Karoński, M., Łuczak, T., Thomason, A.: Edge weights and vertex colours. J. Comb. Theory Ser. B 91, 151–157 (2004)
Lintzmayer, C.N., Mota, G.O., Sambinelli, M.: Decomposing split graphs into locally irregular graphs. Discrete Appl. Math. 292, 33–44 (2021)
Lužar, B., Przybyło, J., Sotsák, R.: New bounds for locally irregular chromatic index of bipartite and subcubic graphs. J. Comb. Optim. 36, 1425–1438 (2018)
Przybyło, J.: On decomposing graphs of large minimum degree into locally irregular subgraphs. Electron. J. Comb. 23, 2–31 (2016)
Sedlar, J., Škrekovski, R.: Remarks on the local irregularity conjecture. Mathematics 9, 3209–3218 (2021)
Acknowledgements
The authors would like to thank the anonymous referees, who made numerous constructive suggestions that led to improvements on the presentation of this paper. Lei was partially supported by the National Natural Science Foundation of China (No. 12001296) and the Natural Science Foundation of Tianjin (No. 21JCQNJC00060). Lian, Shi and Zhao were partially supported by the National Natural Science Foundation of China (Nos. 11922112 and 12161141006), the Natural Science Foundation of Tianjin (Nos. 20JCJQJC00090 and 20JCZDJC00840), Natural Science Basic Research Program of Shaanxi (Program No. 2021JM-422) and the Fundamental Research Funds for the Central Universities, Nankai University.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Martine Labbe.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Lei, H., Lian, X., Shi, Y. et al. Graph Classes with Locally Irregular Chromatic Index at most 4. J Optim Theory Appl 195, 903–918 (2022). https://doi.org/10.1007/s10957-022-02119-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-022-02119-7