Vertex distinguishing colorings of graphs

Graphs, Hypergraphs, and Computing

25 February 15:30 - 16:30

Mariusz Wozniak - AGH University of Science and Technology

Let us consider a coloring f of edges in a simple graph G=(V,E). Such a coloring defines for each vertex x of G 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 edge coloring 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 (or total) coloring 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 and 1-2 Conjecture, respectively.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to