|
||
|
Z grubsza rzecz biorąc, chodzi tu o szeroko rozumiany problem rozróżniania wierzchołków grafu. Rozróżnienie to wynika w ten czy inny sposób z kolorowania krawędzi grafu (lub krawędzi i wierzchołków). Zagadnienia tego typu rozważane są od dawna, jednak problemy kolorowania krawędzi w sposób rozróżniający sąsiadów pojawiły się dopiero w XXI wieku zyskując od razu duże zainteresowanie. Chodzi o właściwe lub dowolne, czyli niekoniecznie właściwe, kolorowanie krawędzi grafu tak, by przypisane wierzchołkom zbiory kolorów krawędzi incydentnych (palety) były różne dla wierzchołków sąsiednich. Jeśli kolorowanie jest ogólne to możemy m.in. rozważać zbiory jak i multizbiory kolorów. Z reguły jako kolory występują liczby naturalne (ze {1,2,...,k}), w związku z czym możliwe są też operacje arytmetyczne na kolorach. Szczególną popularnością wśród tych zagadnień cieszy się rozróżnianie sąsiednich wierzchołków za pomoca sum kolorów występujących przy danym wierzchołku. Wtedy kolor krawędzi może być interpretowany jako krotność krawędzi, a ww. suma jako stopień wierzchołka w multigrafie otrzymanym przez zastąpienie krawędzi multikrawędziami. Na popularność tę ma zapewne wpływ elegancja i prostota słynnej już hipotezy 1-2-3, która mówi, że trzy liczby 1, 2, 3 zawsze wystarczą do uzyskania rozróżnienia wierzchołków sąsiednich, o ile graf nie ma krawędzi izolowanych.
Inne podejście do zagadnienia rozróżniania wierzchołków opiera się na pojęciu grafu lokalnie nieregularnego (tj. na grafu niemającego sąsiednich wierzchołków o tym samym stopniu) oraz na rozkładach grafu na części lokalnie nieregularne.
Przegląd (niektórych) wyników do roku 2016 zawiera m.in. referat "Vertex distinguishing colorings of graphs" wygłoszony na seminarium w Laboratore de Recherche en Informatique, Orsay, Saclay w 2016 roku.
