Rafał KALINOWSKI

Kolorowania rozróżniające krawędzie

Otoczeniem krawędzi e w grafie G nazywamy jego podgraf $N[e]$ indukowany przez krawędź e oraz krawędzie sąsiednie. Mówimy, że kolorowanie krawędzi grafu G rozróżnia krawędzie $e_1$ i $e_2$, jeżeli nie istnieje izomorfizm $\varphi$ otoczeń $N[e_1]$ i $N[e_2]$ zachowujący kolory i taki, że $\varphi (e_1)=\varphi (e_2)$. Najmniejszą liczbę kolorów w kolorowaniu rozróżniającym każdą parę krawędzi grafu G nazywamy indeksem rozróżniającym krawędzie grafu G i oznaczamy $\chi '_e(G)$.

Przedstawione zostaną wyniki uzyskane wspólnie z Mariuszem Woźniakiem, dotyczące indeksu rozróżniającego krawędzie dla pewnych klas grafów.

Serdecznie zapraszamy wszystkich chętnych !