VERTEX DISTINGUISHING COLORINGS OF GRAPHS
Time: 11:30 -- Location: LRI, 435, salle des theses
Abstract : Let us consider a coloring \(f\) of edges in a simple graph \(G = (V, E)\). Such acoloring defines for each vertex \(x \in V\) the palette of colors, i.e., the multiset of colors of edges incident with \(x\), denoted by \(S(x)\). These palettes can be used to distinguish the vertices of the graph. There are many papers dealing with distinguishing either all or only neighboring vertices in a graph. In the first part of my talk we shall consider proper coloring f of G and we shall distinguish all vertices of the graph. We shall show that if we distinguish the vertices by sets of color walks starting from vertices, not just by their palettes, then the number of colors we need is very close to the chromatic index. Some relationships to other ‘distinguishing’ parameters will be discussed such as the distinguishing chromatic index, i.e., the minimum number of colors in a proper edge-coloring preserved only by the identity automorphism. In the second part, we shall consider general edge coloring f of G and we shall distinguish only adjacent vertices. I’ll present some new ideas and problems. These concepts are closely related to the known \(1-2-3\) Conjecture.