Remarks on the Local Irregularity Conjecture

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

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;

Data

Language:	English
Year of publishing:	2021
Typology:	1.01 - Original Scientific Article
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.17
COBISS:	93453315
ISSN:	2227-7390
Views:	101
Downloads:	24
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Opombe o domnevi o lokalni iregularnosti
Secondary keywords:	lokalno iregularno barvanje povezav;domneva o lokalni iregularnosti;uniciklični graf;kaktus graf;
Type (COBISS):	Article
Pages:	str. 1-10
Volume:	ǂVol. ǂ9
Issue:	ǂiss. ǂ24
Chronology:	2021
DOI:	10.3390/math9243209
ID:	15288102