Sylwia Cichacz ; Jakub Przybylo - Irregular edge coloring of 2-regular graphs

dmtcs:544 - Discrete Mathematics & Theoretical Computer Science, February 5, 2011, Vol. 13 no. 1 -
Irregular edge coloring of 2-regular graphsArticle

Authors: Sylwia Cichacz 1; Jakub Przybylo 1

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.

Volume: Vol. 13 no. 1
Section: Graph and Algorithms
Published on: February 5, 2011
Accepted on: June 9, 2015
Submitted on: July 9, 2009
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 353 times.
This article's PDF has been downloaded 311 times.