Author(s):
1. Jelena Sedlar:
University of Split, Faculty of Civil Engineering, Architecture and Geodesy, 21000 Split; Croatia Faculty of Information Studies, 8000 Novo Mesto, Slovenia
2. Riste Sˇ krekovski:
University of Ljubljana, Faculty of Mathematics and Physics, 1000 Ljubljana, Slovenia;Faculty of Information Studies, 8000 Novo Mesto, Slovenia
Abstract:
A graph is locally irregular if the degrees of the end-vertices of every edge are distinct. An edge coloring of a graph G is locally irregular if every color induces a locally irregular subgraph of G. A colorable graph G is any graph which admits a locally irregular edge coloring. The locally irregular chromatic index i0rr(G) of a colorable graph G is the smallest number of colors required by a locally irregular edge coloring of G. The Local Irregularity Conjecture claims that all colorable graphs require at most 3 colors for a locally irregular edge coloring. Recently, it has been observed that the conjecture does not hold for the bow-tie graph B, since B is colorable and requires at least 4 colors for a locally irregular edge coloring. Since B is a cactus graph and all non-colorable graphs are also cacti, this seems to be a relevant class of graphs for the Local Irregularity Conjecture. In this paper, it is proved that i0rr(G) 4 for all colorable cactus graphs.
Page(s):
1-6
Published:
Journal: Discrete Mathematics Letters, Volume: 11, Issue: 0, Year: 2023
Keywords:
cactus graph
,
Local Irregularity Conjecture
,
locally irregular edge coloring
References:
References are not available for this document.
Citations
Citations are not available for this document.