Irregular edge coloring of 2-regular graphs
Sylwia Cichacz-Przenioslo, Jakub Przybyło
Abstract
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.
Full Text: PDF PostScript