Remarks on the local irregularity conjecture

Sedlar, Jelena (avtor), Škrekovski, Riste (avtor)

A locally irregular graph is a graph in which the end vertices of every edge have distinct degrees. A locally irregular edge coloring of a graph G is any edge coloring of G such that each of the colors induces a locally irregular subgraph of G. A graph G is colorable if it allows a locally irregular edge coloring. The locally irregular chromatic index of a colorable graph G, denoted by χ$^′_{irr}$(G), is the smallest number of colors used by a locally irregular edge coloring of G. The local irregularity conjecture claims that all graphs, except odd-length paths, odd-length cycles and a certain class of cacti are colorable by three colors. As the conjecture is valid for graphs with a large minimum degree and all non-colorable graphs are vertex disjoint cacti, we study rather sparse graphs. In this paper, we give a cactus graph B which contradicts this conjecture, i.e., χ$^′_{irr}$(B) = 4. Nevertheless, we show that the conjecture holds for unicyclic graphs and cacti with vertex disjoint cycles.

• Jezik: Angleški jezik
• Ključne besede: locally irregular edge coloring, local irregularity conjecture, unicyclic graph, cactus graph
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2021
• Št. strani: 10 str.
• Številčenje: Vol. 9, iss. 24, art. 3209
• PID: 20.500.12556/RUL-136571
• UDK: 519.17
• ISSN pri članku: 2227-7390
• DOI: 10.3390/math9243209
• COBISS.SI-ID: 93453315
• Datum objave v RUL: 11.05.2022

Gradivo je del revije

• Naslov: Mathematics
• Skrajšan naslov: Mathematics
• Založnik: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.
• Začetek licenciranja: 12.12.2021

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: lokalno iregularno barvanje povezav, domneva o lokalni iregularnosti, uniciklični graf, kaktus graf