Powiadomienia systemowe
- Sesja wygasła!
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
A multigraph is locally irregular if the degrees of the end-vertices of every multiedge are distinct. The locally irregular coloring is an edge coloring of a multigraph G such that every color induces a locally irregular submultigraph of G. A locally irregular colorable multigraph G is any multigraph which admits a locally irregular coloring. We denote by lir(G) the locally irregular chromatic index of a multigraph G, which is the smallest number of colors required in the locally irregular coloring of the locally irregular colorable multigraph G. In case of graphs the definitions are similar. The Local Irregularity Conjecture for 2-multigraphs claims that for every connected graph G, which is not isomorphic to K2, multigraph 2G obtained from G by doubling each edge satisfies lir(2G) ≤ 2. We show this conjecture for cacti. This class of graphs is important for the Local Irregularity Conjecture for 2-multigraphs and the Local Irregularity Conjecture which claims that every locally irregular colorable graph G satisfies lir(G) ≤ 3. At the beginning it has been observed that all not locally irregular colorable graphs are cacti. Recently it has been proved that there is only one cactus which requires 4 colors for a locally irregular coloring and therefore the Local Irregularity Conjecture was disproved.
Słowa kluczowe
Czasopismo
Rocznik
Tom
Strony
49--65
Opis fizyczny
Bibliogr. 12 poz., rys.
Twórcy
autor
- AGH University of Krakow, Faculty of Applied Mathematics, Department of Discrete Mathematics, al. A. Mickiewicza 30, 30–059 Kraków, Poland
autor
- AGH University of Krakow, Faculty of Applied Mathematics, Department of Discrete Mathematics, al. A. Mickiewicza 30, 30–059 Kraków, Poland
Bibliografia
- [1] O. Baudon, J. Bensmail, É. Sopena, On the complexity of determining the irregular chromatic index of a graph, J. Discret. Algorithms 30 (2015), 113–127.
- [2] O. Baudon, J. Bensmail, J. Przybyło, M. Woźniak, On decomposing regular graphs into locally irregular subgraphs, European J. Combin. 49 (2015), 90–104.
- [3] J. Bensmail, F. Dross, N. Nisse, Decomposing degenerate graphs into locally irregular subgraphs, Graphs Comb. 36 (2020), 1869–1889.
- [4] J. Bensmail, M. Merker, C. Thomassen, Decomposing graphs into a constant number of locally irregular subgraphs, European J. Combin. 60 (2017), 124–134.
- [5] I. Grzelec, M. Woźniak, On decomposing multigraphs into locally irregular submultigraphs, Appl. Math. Comput. 452 (2023), 128049.
- [6] M. Karoński, T. Łuczak, A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B 91 (2004), 151–157.
- [7] C.N. Lintzmayer, G.O. Mota, M. Sambinelli, Decomposing split graphs into locally irregular graphs, Discrete Appl. Math. 292 (2021), 33–44.
- [8] B. Lužar, M. Maceková, S. Rindošová, R. Soták, K. Sroková, K. Štorgel, Locally irregular edge-coloring of subcubic graphs, arXiv:2210.04649.
- [9] B. Lužar, J. Przybyło, R. Soták, New bounds for locally irregular chromatic index of bipartite and subcubic graphs, J. Comb. Optim. 36 (2018), 1425–1438.
- [10] J. Przybyło, On decomposing graphs of large minimum degree into locally irregular subgraphs, Electron. J. Combin. 23 (2016), 2–31.
- [11] J. Sedlar, R. Škrekovski, Local irregularity conjecture vs. cacti, arXiv:2207.03941.
- [12] J. Sedlar, R. Škrekovski, Remarks on the Local Irregularity Conjecture, Mathematics 2021, 9(24), 3209.
Uwagi
Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-fb201489-abd2-4f99-b3be-d778e4632a48