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.