On decomposing multigraphs into locally irregular submultigraphs

Igor Grzelec and Mariusz Woźniak

Applied Mathematics and Computation, 2023, vol. 452, issue C

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 G such that every color induces a locally irregular submultigraph of G. We say that a multigraph G is locally irregular colorable if it admits a locally irregular edge coloring and we denote by lir(G) the locally irregular chromatic index of G, which is the smallest number of colors required in a locally irregular edge coloring of a locally irregular colorable multigraph G. We conjecture that for every connected graph G, which is not isomorphic to K2, the multigraph 2G obtained from G by doubling each edge admits lir(2G)≤2. 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 k-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.

Keywords: Locally irregular graphs and multigraphs; Decomposition of graphs and multigraphs (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300323002187
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:452:y:2023:i:c:s0096300323002187

DOI: 10.1016/j.amc.2023.128049

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().