19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Edge-distinguishing index of a graph
Presented by Rafal KALINOWSKI
Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs
Content
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.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled