Let G be a simple graph and let us color its edges so that the multisets of colors around each vertex are distinct. The smallest number of colors for which such a coloring exists is called the irregular coloring number of G and is denoted by c(G). We determine the exact value of the irregular coloring number for almost all 2-regular graphs. The results obtained provide new examples demonstrating that a conjecture by Burris is false. As another consequence, we also determine the value of a graph invariant called the point distinguishing index (where sets, instead of multisets, are required to be distinct) for the same family of graphs.

Source : oai:HAL:hal-00990495v1

Volume: Vol. 13 no. 1

Section: Graph and Algorithms

Published on: February 5, 2011

Submitted on: July 9, 2009

Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 138 times.

This article's PDF has been downloaded 185 times.