Remarks on the local irregularity conjecture

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

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.

• Language: English
• Keywords: locally irregular edge coloring, local irregularity conjecture, unicyclic graph, cactus graph
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2021
• Number of pages: 10 str.
• Numbering: Vol. 9, iss. 24, art. 3209
• PID: 20.500.12556/RUL-136571
• UDC: 519.17
• ISSN on article: 2227-7390
• DOI: 10.3390/math9243209
• COBISS.SI-ID: 93453315
• Publication date in RUL: 11.05.2022

Record is a part of a journal

• Title: Mathematics
• Shortened title: Mathematics
• Publisher: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.
• Licensing start date: 12.12.2021

Secondary language

• Language: Slovenian
• Keywords: lokalno iregularno barvanje povezav, domneva o lokalni iregularnosti, uniciklični graf, kaktus graf