Cichacz, Sylwia and Przybylo, Jakub - 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 graphs

Authors: Cichacz, Sylwia and Przybylo, Jakub

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]


Browsing statistics

This page has been seen 40 times.
This article's PDF has been downloaded 52 times.