Szczegóły publikacji
Opis bibliograficzny
On decomposing multigraphs into locally irregular submultigraphs / Igor GRZELEC, Mariusz WOŹNIAK // Applied Mathematics and Computation ; ISSN 0096-3003. — 2023 — vol. 452 art. no. 128049, s. 1-7. — Bibliogr. s. 7, Abstr. — Publikacja dostępna online od: 2023-04-21
Autorzy (2)
Słowa kluczowe
Dane bibliometryczne
ID BaDAP | 146456 |
---|---|
Data dodania do BaDAP | 2023-05-16 |
Tekst źródłowy | URL |
DOI | 10.1016/j.amc.2023.128049 |
Rok publikacji | 2023 |
Typ publikacji | artykuł w czasopiśmie |
Otwarty dostęp | |
Czasopismo/seria | Applied Mathematics and Computation |
Abstract
A locally irregular multigraph is a multigraph whose adjacent vertices have distinct degrees. The locally irregular edge coloring is an edge coloring of a multigraph such that every color induces a locally irregular submultigraph of . We say that a multigraph is locally irregular colorable if it admits a locally irregular edge coloring and we denote by the locally irregular chromatic index of , which is the smallest number of colors required in a locally irregular edge coloring of a locally irregular colorable multigraph . We conjecture that for every connected graph , which is not isomorphic to , the multigraph obtained from by doubling each edge admits . This concept is closely related to the well known 1-2-3 Conjecture, Local Irregularity Conjecture, (2, 2) Conjecture and other similar problems concerning edge colorings. We show this conjecture holds for graph classes like paths, cycles, wheels, complete graphs, complete -partite graphs and bipartite graphs. We also prove the general bound for locally irregular chromatic index for all 2-multigraphs using our result for bipartite graphs.