19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Edge-distinguishing index of a graph

Presented by Rafal KALINOWSKI
Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs


We introduce a concept of edge-distinguishing colourings of graphs. A closed neighbourhood of an edge e in a graph G is a subgraph N[e]induced by e and all edges adjacent to it. We say that a coloring c: E(G) → C distinguishes two edges e and e’ if there does not exist an isomorphism φ of N[e] onto N[e’] such that φ(e)=e’, and φ preserves colours of c. An edge-distinguishing index of a graph G is the minimum number of colours in a proper colouring of edges of G, which distinguishes every two distinct edges. Such a colouring is called edge-distinguishing. We determine the edge-distinguishing index for cycles, paths, complete graphs and complete bipartite graphs.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors