Jakub PRZYBYŁO

(WMS, AGH)

Hipoteza 1,2

Niech k-totalne waźenie grafu prostego G oznacza nadanie wag naturalnych ze zbioru $\{1, . . . , k\}$ wszystkim krawędziom oraz wierzchołkom grafu $G$. W konsekwencji otrzymujemy kolorowanie wierzchołkowe przez sumy wag krawędzi incydentnych z wierzchołkiem oraz wagi samego wierzchołka. Nawiązując do Hipotezy 1,2,3 Karońskiego, Łuczaka i Thomasona, pytamy, czy moźemy uzyskać właściwe kolorowanie uźywając jedynie wag 1 i 2 dla dowolnego grafu $G$? Jest tak między innymi dla grafów 3-kolorowalnych, pełnych oraz grafów 4-regularnych. Omówione zostaną te wyniki oraz wskazane pewne ograniczenia od góry na rozwaźany parametr. W szczególności, wystarczy uźyć wag od 1 do 11, jak i od 1 do $\frac{\chi(G)}{2}+1$ dla dowolnego grafu $G$.

Serdecznie zapraszamy wszystkich chętnych !