Local irregularity conjecture for 2-multigraphs versus cacti
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 a...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AGH Univeristy of Science and Technology Press
2023-10-01
|
| Series: | Opuscula Mathematica |
| Subjects: | |
| Online Access: | https://www.opuscula.agh.edu.pl/vol44/1/art/opuscula_math_4403.pdf |
| _version_ | 1797648273630035968 |
|---|---|
| author | Igor Grzelec Mariusz Woźniak |
| author_facet | Igor Grzelec Mariusz Woźniak |
| author_sort | Igor Grzelec |
| collection | DOAJ |
| description | 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 \(\textrm{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 \(K_2\), multigraph \(^2G\) obtained from \(G\) by doubling each edge satisfies \(\textrm{lir}(^2G)\leq 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 \(\textrm{lir}(G)\leq 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. |
| first_indexed | 2024-03-11T15:28:44Z |
| format | Article |
| id | doaj.art-112c14839902468cbb6c701045eb96d2 |
| institution | Directory Open Access Journal |
| issn | 1232-9274 |
| language | English |
| last_indexed | 2024-03-11T15:28:44Z |
| publishDate | 2023-10-01 |
| publisher | AGH Univeristy of Science and Technology Press |
| record_format | Article |
| series | Opuscula Mathematica |
| spelling | doaj.art-112c14839902468cbb6c701045eb96d22023-10-27T07:34:03ZengAGH Univeristy of Science and Technology PressOpuscula Mathematica1232-92742023-10-014414965https://doi.org/10.7494/OpMath.2024.44.1.494403Local irregularity conjecture for 2-multigraphs versus cactiIgor Grzelec0https://orcid.org/0000-0002-1011-535XMariusz Woźniak1https://orcid.org/0000-0003-4769-0056AGH University of Krakow, Faculty of Applied Mathematics, Department of Discrete Mathematics, al. A. Mickiewicza 30, 30-059 Kraków, PolandAGH University of Krakow, Faculty of Applied Mathematics, Department of Discrete Mathematics, al. A. Mickiewicza 30, 30-059 Kraków, PolandA 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 \(\textrm{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 \(K_2\), multigraph \(^2G\) obtained from \(G\) by doubling each edge satisfies \(\textrm{lir}(^2G)\leq 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 \(\textrm{lir}(G)\leq 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.https://www.opuscula.agh.edu.pl/vol44/1/art/opuscula_math_4403.pdflocally irregular coloringdecomposablecactus graphs2-multigraphs |
| spellingShingle | Igor Grzelec Mariusz Woźniak Local irregularity conjecture for 2-multigraphs versus cacti Opuscula Mathematica locally irregular coloring decomposable cactus graphs 2-multigraphs |
| title | Local irregularity conjecture for 2-multigraphs versus cacti |
| title_full | Local irregularity conjecture for 2-multigraphs versus cacti |
| title_fullStr | Local irregularity conjecture for 2-multigraphs versus cacti |
| title_full_unstemmed | Local irregularity conjecture for 2-multigraphs versus cacti |
| title_short | Local irregularity conjecture for 2-multigraphs versus cacti |
| title_sort | local irregularity conjecture for 2 multigraphs versus cacti |
| topic | locally irregular coloring decomposable cactus graphs 2-multigraphs |
| url | https://www.opuscula.agh.edu.pl/vol44/1/art/opuscula_math_4403.pdf |
| work_keys_str_mv | AT igorgrzelec localirregularityconjecturefor2multigraphsversuscacti AT mariuszwozniak localirregularityconjecturefor2multigraphsversuscacti |