Local Irregularity Conjecture vs. cacti

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 X'irr(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 locally irregular edge coloring. Recently, it has been observed that the conjecture does not hold for the bow-tie graph B [7]. Cacti are important class of graphs for this conjecture since B and all non-colorable graphs are cacti. In this paper we show that for every colorable cactus graph G != B it holds that X'irr(G) <= 3. This makes us to believe that B is the only colorable graph with X'irr(B) > 3, and consequently that B is the only counterexample to the Local Irregularity Conjecture.

No reviews yet.

No comments yet.