Wyróżniająca się kolorystyka

Rozróżnianie kolorowania wykresu 4- hipersześcianu

W teorii grafów wyróżniające kolorowanie lub wyróżniające etykietowanie grafu to przypisanie kolorów lub etykiet do wierzchołków grafu, które niszczy wszystkie nietrywialne symetrie grafu . Kolorystyka nie musi być odpowiednia : sąsiednie wierzchołki mogą mieć ten sam kolor. W przypadku wykresu kolorowego nie powinno istnieć żadne odwzorowanie wierzchołków na siebie nawzajem, które zachowuje zarówno przyleganie, jak i kolorowanie. Minimalna liczba kolorów w kolorystyce wyróżniającej nazywana jest liczbą wyróżniającą wykresu.

Rozróżniające kolory i rozróżniające liczby zostały wprowadzone przez Albertsona i Collinsa (1996) , którzy podali następujący motywujący przykład, oparty na zagadce sformułowanej wcześniej przez Franka Rubina: „Załóżmy, że masz pęk kluczy do różnych drzwi; każdy klucz otwiera tylko jedne drzwi , ale dla ciebie wszystkie wyglądają nie do odróżnienia. Ile kolorów potrzebujesz, aby pokolorować uchwyty klawiszy w taki sposób, abyś mógł jednoznacznie zidentyfikować każdy klucz? Ten przykład został rozwiązany przy użyciu wyróżniającej kolorystyki wykresu cyklu . Dzięki takiej kolorystyce każdy klawisz będzie jednoznacznie identyfikowany na podstawie koloru i otaczającej go sekwencji kolorów.

Przykłady

Osiem asymetrycznych wykresów, z których każdy ma wyróżniającą kolorystykę z tylko jednym kolorem (czerwonym)

Graf ma wyróżniający numer jeden wtedy i tylko wtedy, gdy jest asymetryczny . Na przykład wykres Fruchta ma wyróżniającą kolorystykę z tylko jednym kolorem.

W pełnym grafie jedyne rozróżniające kolory przypisują każdemu wierzchołkowi inny kolor. Bo gdyby dwóm wierzchołkom przypisano ten sam kolor, istniałaby symetria, która zamieniłaby te dwa wierzchołki, pozostawiając resztę na miejscu. Dlatego numerem wyróżniającym pełnego wykresu K _n jest n . Jednak wykres otrzymany z K _n przez dołączenie wierzchołka stopnia pierwszego do każdego wierzchołka K _n ma znacznie mniejszą liczbę wyróżniającą, pomimo tej samej grupy symetrii: ma wyróżniającą kolorystykę z ${\ Displaystyle \ lceil { \sqrt {n}}\rceil }$ kolory, otrzymane przez użycie innej uporządkowanej pary kolorów dla każdej pary wierzchołka K _n i sąsiada z nim połączonego.

Wyróżniająca się kolorystyka pierścienia z sześcioma kluczami, przy użyciu dwóch kolorów (czerwonego i niepomalowanego)

W przypadku wykresu cyklu składającego się z trzech, czterech lub pięciu wierzchołków potrzebne są trzy kolory, aby skonstruować wyróżniającą kolorystykę. Na przykład każde dwukolorowe pięciocyklowe ma symetrię odbicia. W każdym z tych cykli przypisanie unikalnego koloru każdemu z dwóch sąsiednich wierzchołków i użycie trzeciego koloru dla wszystkich pozostałych wierzchołków skutkuje trójkolorowym kolorowaniem wyróżniającym. Jednak cykle składające się z sześciu lub więcej wierzchołków mają wyróżniające się kolory tylko w dwóch kolorach. Oznacza to, że układanka pęku kluczy Franka Rubina wymaga trzech kolorów dla pierścieni z trzema, czterema lub pięcioma kluczami, ale tylko dwóch kolorów dla sześciu lub więcej kluczy lub dla dwóch kluczy. Na przykład w pokazanym pierścieniu sześciu kluczy każdy klucz można odróżnić po kolorze i długości lub długościach sąsiednich bloków kluczy o przeciwnych kolorach: istnieje tylko jeden klucz dla każdej kombinacji koloru klucza i długości sąsiednich bloków .

Wykresy hipersześcianu wykazują podobne zjawisko do wykresów cyklicznych. Dwu- i trójwymiarowe wykresy hipersześcianu (odpowiednio 4-cykl i wykres sześcianu) mają wyróżniającą liczbę trzy. Jednak każdy graf hipersześcianu o wyższym wymiarze ma wyróżniającą liczbę tylko dwa.

Wykres Petersena ma numer wyróżniający 3. Jednak poza tym wykresem i pełnymi wykresami wszystkie wykresy Knesera mają numer wyróżniający 2. Podobnie wśród uogólnionych grafów Petersena tylko sam wykres Petersena i wykres sześcianu mają numer wyróżniający 3; reszta ma numer wyróżniający 2.

Złożoność obliczeniowa

Liczby wyróżniające drzew , grafy planarne i grafy interwałowe można obliczyć w czasie wielomianowym .

Dokładna złożoność obliczania liczb wyróżniających jest niejasna, ponieważ jest ściśle związana z wciąż nieznaną złożonością izomorfizmu grafów . Jednak wykazano, że należy do klasy złożoności AM . Ponadto sprawdzenie, czy wyróżniająca liczba chromatyczna wynosi co najwyżej trzy, jest NP-trudne , a sprawdzenie, czy wynosi co najwyżej dwa, jest „co najmniej tak trudne jak automorfizm grafu, ale nie trudniejsze niż izomorfizm grafu”.

Dodatkowe właściwości

Zabarwienie danego grafu jest wyróżnikiem dla tego grafu wtedy i tylko wtedy, gdy jest wyróżnikiem dla grafu dopełnienia . Dlatego każdy wykres ma taką samą liczbę wyróżniającą, jak jego uzupełnienie.

Dla każdego wykresu G liczba wyróżniająca G jest co najwyżej proporcjonalna do logarytmu liczby automorfizmów G . Jeśli automorfizmy tworzą nietrywialną grupę abelową , liczbą wyróżniającą są dwa, a jeśli tworzy grupę dwuścienną , wówczas liczbą wyróżniającą jest co najwyżej trzy.

Dla każdej grupy skończonej istnieje graf, w którym ta grupa jest grupą automorfizmów, z wyróżnikiem numer dwa. Wynik ten rozszerza twierdzenie Fruchta , że ​​każda skończona grupa może być zrealizowana jako grupa symetrii wykresu.

Wariacje

Właściwa kolorystyka wyróżniająca to kolorystyka wyróżniająca, która jest również właściwą kolorystyką: każde dwa sąsiednie wierzchołki mają różne kolory. Minimalna liczba kolorów w odpowiednim zabarwieniu rozróżniającym grafu nazywana jest wyróżniającą liczbą chromatyczną grafu.