Vertex-distinguishing edge-colorings of sums of paths
Sylwia Cichacz · 2007
In the PhD thesis by Burris (Memphis (1993)), a conjecture was made concerning the number of colors c(G) required to edge-color a simple graph G so that each vertex has a distinct multiset of colors incident to it. We find the exact value of c(G) - the irregular coloring number, and hence verify the conjecture when G is a vertex-disjoint union of paths. We also investigate the point-distinguishing chromatic index, 0(G), where sets, instead of multisets, are required to be distinct, and determine its value for the same family of graphs.