$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Zakładu Matematyki Dyskretnej
Wydziału Matematyki Stosowanej
AGH

We wtorek, 6 listopada 2001 roku, o godzinie 12:45

w sali 304, łącznik A-3-A-4, A G H

Mirko HORNÁK

(Uniwersytet P. J. Szafarika, Koszyce, Sowacja)

wygłosi referat pod tytułem:

Indeks chromatyczny rozróżniający

wierzchołki dla grafu $K_{n,n}$

Niech $G$ będzie grafem, który nie ma składowej $K_2$ i ma co najwyzej jedną składową $K_1$. Jezeli krawedzie grafu $G$ sa pokolorowane, to zbiór kolorów krawedzi incydentnych z wierzcho

kiem $x$ nazywamy paletą wierzcho

ka $x$. Kolorowanie krawedzi grafu $G$ rozróznia jego wierzcho

ki, jezeli rózne wierzcho

ki maja rózne palety. Indeks chromatyczny rozrózniajacy wierzcho

ki grafu $G$, $\chi_0(G)$, jest najmniejszą liczbą kolorów w kolorowaniu krawedzi $G$ rozrózniajacym jego wierzcho

ki.

Dla grafów $K_{n,n}$ wiadomo (Zagaglia Salvi), ze ciag $\{\chi_0(K_{n,n})\}_{n=2}^{\infty}$ jest niemalejacy i zawiera wszystkie liczby cakowite $\ge3$. Dla $k\ge3$ definiujemy liczbę $n_k$ jako najwieksze $n$ takie, ze $\chi_0(K_{n,n})=k$. Liczby $n_k$ sa znane tylko dla $k\le7$: $n_3=2$, $n_4=5$, $n_5=11$, $n_6=22$ i $n_7=46$. Nietrudno wykazac, ze $n_k<2^{k-1}$ i $n_{k+1}\ge2n_k$. Z tego wynika, że $\frac{n_k}{2^{k-1}}\le\frac{n_{k+1}}{2^k}<1$. A zatem granica $l =\lim_{k\to\infty}\frac{n_k}{2^{k-1}}$ istnieje i $0.71875=\frac{46}{64}\le l\le1$. Przedmiotem referatu bedzie szkic dowodu, ze $l\ge3-\sqrt5=0.7639\dots$ .

Hipoteza (Hornák i Soták). $l=3-\sqrt5$.

Problem. Udowodnic przynajmniej, ze $l<1$.

Serdecznie zapraszamy wszystkich chętnych !