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

Povzetek

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.

Ključne besede

locally irregular edge coloring;local irregularity conjecture;unicyclic graph;cactus graph;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UL FMF - Fakulteta za matematiko in fiziko
UDK: 519.17
COBISS: 93453315 Povezava se bo odprla v novem oknu
ISSN: 2227-7390
Št. ogledov: 101
Št. prenosov: 24
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarni naslov: Opombe o domnevi o lokalni iregularnosti
Sekundarne ključne besede: lokalno iregularno barvanje povezav;domneva o lokalni iregularnosti;uniciklični graf;kaktus graf;
Vrsta dela (COBISS): Članek v reviji
Strani: str. 1-10
Letnik: ǂVol. ǂ9
Zvezek: ǂiss. ǂ24
Čas izdaje: 2021
DOI: 10.3390/math9243209
ID: 15288102
Priporočena dela:
, ni podatka o podnaslovu
, delo diplomskega seminarja
, magistrsko delo