On Local Irregularity Conjecture for 2-multigraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929616911859712 |
|---|---|
| author | Grzelec, Igor Onderko, Alfréd Woźniak, Mariusz |
| author_facet | Grzelec, Igor Onderko, Alfréd Woźniak, Mariusz |
| contents | A multigraph in which adjacent vertices have different degrees is called locally irregular. The locally irregular edge coloring is an edge coloring of a multigraph $G$ in which every color induces a locally irregular submultigraph of $G$. We denote by $\operatorname{lir}(G)$ the locally irregular chromatic index of a multigraph $G$, which is the smallest number of colors required in a locally irregular edge coloring of $G$, given that such a coloring of $G$ exists. By $^2G$ we denote a 2-multigraph obtained from a simple graph $G$ by doubling each its edge. In 2022 Grzelec and Woźniak conjectured that $\operatorname{lir}(^2G) \leq 2$ for every connected simple graph $G$ different from $K_2$; the conjecture is known as Local Irregularity Conjecture for 2-multigraphs. In this paper, we prove this conjecture in the case of regular graphs, split graphs, and some particular families of subcubic graphs. Moreover, we provide a constant upper bound on the locally irregular chromatic index of planar 2-multigraphs (except for $^2K_2$), and we obtain a better constant upper bound on $\operatorname{lir}(^2G)$ if $G$ is a simple subcubic graph different from $K_2$. In the proofs, special decompositions of graphs and the relation of Local Irregularity Conjecture to the well-known 1-2-3 Conjecture are utilized. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_04200 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Local Irregularity Conjecture for 2-multigraphs Grzelec, Igor Onderko, Alfréd Woźniak, Mariusz Combinatorics 05c15 A multigraph in which adjacent vertices have different degrees is called locally irregular. The locally irregular edge coloring is an edge coloring of a multigraph $G$ in which every color induces a locally irregular submultigraph of $G$. We denote by $\operatorname{lir}(G)$ the locally irregular chromatic index of a multigraph $G$, which is the smallest number of colors required in a locally irregular edge coloring of $G$, given that such a coloring of $G$ exists. By $^2G$ we denote a 2-multigraph obtained from a simple graph $G$ by doubling each its edge. In 2022 Grzelec and Woźniak conjectured that $\operatorname{lir}(^2G) \leq 2$ for every connected simple graph $G$ different from $K_2$; the conjecture is known as Local Irregularity Conjecture for 2-multigraphs. In this paper, we prove this conjecture in the case of regular graphs, split graphs, and some particular families of subcubic graphs. Moreover, we provide a constant upper bound on the locally irregular chromatic index of planar 2-multigraphs (except for $^2K_2$), and we obtain a better constant upper bound on $\operatorname{lir}(^2G)$ if $G$ is a simple subcubic graph different from $K_2$. In the proofs, special decompositions of graphs and the relation of Local Irregularity Conjecture to the well-known 1-2-3 Conjecture are utilized. |
| title | On Local Irregularity Conjecture for 2-multigraphs |
| topic | Combinatorics 05c15 |
| url | https://arxiv.org/abs/2412.04200 |