\begin{picture}(30,20) \put(0,0){\circle*{2}} \put(30,0){\circle*{2}} \put(0... ... \put(20,10){\line(-2,1){20}} \bezier{150}(14,12)(15,15)(16,13) \end{picture}


$\textstyle \parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Matematyka Dyskretna
(prowadzone przez M.Woźniaka)


We wtorek, 24 stycznia 2006 roku, o godzinie 13:30
w sali 304, łącznik A-3-A-4, A G H


Mirko HORNIAK
(Uniwersytet P. J. Szafarika, Koszyce, Słowacja)


wygłosi referat pod tytułem:


Ogólny indeks rozrózniajacy sąsiadów


Ogólnym indeksem rozróżniającym sąsiadów grafu $ G$ (general neighbour-distinguishing index, $ \mathrm{gndi}(G)$) nazywamy najmniejsze $ k\in\mathbb{Z}$ takie, że krawędzie $ G$ można pokolorować $ k$ kolorami w ten sposób, że sąsiednie wierzchołki mają różne zbiory kolorów (tj. zbiory zawierające kolory krawędzi z nimi incydentnych). Pokażemy, że jeżeli $ \log_2\chi(G)\notin\mathbb{Z}$, to $ \mathrm{gndi}(G)=\lceil\log_2\chi(G)\rceil+1$. Z drugiej strony, jeżeli $ \chi(G)=2^l$, $ l\in\mathbb{Z}^+$, to $ l+1\le\mathrm{gndi}(G)\le l+2$.
 
Serdecznie zapraszamy wszystkich chetnych !