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 - https://doi.org/10.46298/dmtcs.544
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 315 times.
This article's PDF has been downloaded 283 times.