Remarks on the Local Irregularity Conjecture

Jelena Sedlar and Riste Škrekovski
Additional contact information
Jelena Sedlar: Faculty of Civil Engineering, Architecture and Geodesy, University of Split, 21000 Split, Croatia
Riste Škrekovski: Faculty of Information Studies, University of Ljubljana, 8000 Novo Mesto, Slovenia

Mathematics, 2021, vol. 9, issue 24, 1-10

Abstract: 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.

Keywords: locally irregular edge coloring; local irregularity conjecture; unicyclic graph; cactus graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/24/3209/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/24/3209/ (text/html)

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:gam:jmathe:v:9:y:2021:i:24:p:3209-:d:700489

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().