Seminar

# 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.

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.

Organizers

Magnus M. Halldorsson

Reykjavik University

Klas Markström

Umeå University

Andrzej Rucinski

Adam Mickiewicz University

Carsten Thomassen

Technical University of Denmark, DTU