Maciej KALKOWSKI

(UAM)

Lokalna i globalna siła nieregularności grafu

Niech $G$ będzie spójnym grafem prostym.

Dla grafu $G$, definiujemy $k$-ważenie jako funkcję $f: E(G) \mapsto \{1,..,k\}$ oraz $k$-totalne-ważenie grafu jako $k$-ważenie, którego funkcja $f$ dodatkowo nadaje jedną wagę wszystkim wierzchołkom $f: E(G) \cup V(G) \mapsto \{1,..k\}$.

Przez kolor wierzchołka $v$ rozumiemy sumę wag krawędzi incydentnych z wierzchołkiem $v$. Analogicznie, totalny kolor wierzchołka $v$, obliczamy jako sumę koloru wierzchołka $v$ i wagi $v$.

Lokalną siłę nieregularności, definiujemy jako najmniejsze $k$, takie że istnieje $k$-ważenie, które umożliwi kolorowanie właściwe grafu. Globalną siłę nieregularności, definiujemy jako najmniejsze $k$, takie że istnieje k-ważenie, które umożliwi nadanie unikalnych kolorów wszystkim wierzchołkom w grafie. Totalna lokalna siła nieregularności i totalna globalna siła nieregularności są definiowane analogicznie.

Na referacie omówię bieżące wyniki i zaprezentuję algorytm 3-totalnego ważenia grafu, uzyskujący kolorowanie właściwe.

Serdecznie zapraszamy wszystkich chętnych!