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 graphs

Authors: Sylwia Cichacz ; Jakub Przybylo

    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 190 times.
    This article's PDF has been downloaded 208 times.