Całkowite zabarwienie - Total coloring

Właściwe całkowite wybarwienie klatki Fostera 6 kolorami. Całkowita liczba chromatyczna tego wykresu jest 6 od stopnia każdego wierzchołka znajduje się 5 (5 + 1 sąsiednie krawędzie wierzchołków = 6).

W teorii wykres , barwiących ogółem jest typu wykres zabarwienia na wierzchołkach i krawędziach grafu. W przypadku użycia bez żadnych zastrzeżeń, całkowite zabarwienie jest zawsze uważane za właściwe w tym sensie, że żadne sąsiednie krawędzie, żadne sąsiednie wierzchołki i żadna krawędź ani żaden wierzchołek końcowy nie mają przypisanego tego samego koloru. Całkowita liczba chromatyczna χ "( G ) grafu G jest najmniejsza liczba kolorów potrzebnych w każdej całkowitej barwienia G .

Całkowity wykres T = T ( G ) grafu G jest wykresem takie, że (i) zestaw wierzchołek T odpowiada na wierzchołkach i krawędziach G i (ii) dwa wierzchołki są obok siebie w T tylko wtedy, gdy odpowiadające im elementy są albo sąsiadujące, albo incydentalne w G . Następnie całkowite wybarwienie G staje się (właściwą) wierzchołka zabarwienie z T ( G ). Całkowite kolorowanie to podział wierzchołków i krawędzi grafu na całkowicie niezależne zbiory .

Niektóre nierówności dla χ″( G ):

1. χ”( G ) ≥ Δ( G ) + 1.
2. χ”( G ) ≤ Δ( G ) + ¹⁰²⁶ . (Molloy, Reed 1998)
3. χ”( G ) ≤ Δ( G ) + 8 ln ⁸ (Δ( G )) dla wystarczająco dużego Δ( G ). (Hind, Molloy, Reed 1998)
4. χ”( G ) ≤ ch′( G ) + 2.

Tutaj Δ( G ) jest maksymalnym stopniem ; oraz ch′( G ), możliwość wyboru krawędzi .

Całkowite zabarwienie powstaje w sposób naturalny, ponieważ jest po prostu mieszanką wybarwień wierzchołków i krawędzi. Następnym krokiem jest wyszukanie dowolnej górnej granicy wpisanej przez Brooks lub Vizing w całkowitej liczbie chromatycznej pod względem maksymalnego stopnia.

Całkowita wersja kolorystyczna górnej granicy maksymalnego stopnia jest trudnym problemem, który wymyka się matematykom od 50 lat. Trywialne dolne ograniczenie dla χ″( G ) to Δ( G ) + 1. Niektóre wykresy, takie jak cykle długości i pełne dwudzielne wykresy postaci, wymagają Δ( G ) + 2 kolory, ale nie znaleziono żadnego wykresu, który wymagałby więcej kolorów . Prowadzi to do spekulacji, że każdy wykres potrzebuje Δ( G ) + 1 lub Δ( G ) + 2 kolory, ale nigdy więcej: ${\displaystyle n\nie \ekwiwalent 0{\bmod {3}}}$${\ Displaystyle K_ {n, n}}$

Całkowite przypuszczenie o kolorystyce ( Behzad , Vizing).${\ Displaystyle \ chi ''(G) \ leq \ Delta (G) + 2.}$

Najwyraźniej termin „całkowite zabarwienie” i stwierdzenie o całkowitym zabarwieniu zostały niezależnie wprowadzone przez Behzada i Vizinga przy wielu okazjach w latach 1964-1968 (patrz Jensen i Toft). Wiadomo, że hipoteza jest słuszna dla kilku ważnych klas grafów, takich jak wszystkie grafy dwudzielne i większość grafów planarnych, z wyjątkiem tych z maksymalnym stopniem 6. Przypadek planarny można zakończyć, jeśli hipoteza grafu planarnego Vizinga jest prawdziwa. Ponadto, jeśli hipoteza kolorowania listy jest prawdziwa, to${\ Displaystyle \ chi ''(G) \ leq \ Delta (G) + 3.}$

Uzyskano wyniki związane z całkowitym zabarwieniem. Na przykład Kilakos i Reed (1993) udowodnili, że ułamkowa liczba chromatyczna całego wykresu grafu G wynosi co najwyżej Δ( G ) + 2.

Bibliografia

• Tył, Hugo; Molloy, Michael; Reed, Bruce (1998). „Całkowite kolorowanie z Δ + poli(log Δ) kolorów”. SIAM Journal on Computing . 28 (3): 816-821. doi : 10.1137/S0097539795294578 .
• Jensen, Tommy R.; Toft, Bjarne (1995). Problemy z kolorowaniem wykresów . Nowy Jork: Wiley-Interscience. ISBN  0-471-02865-7 .
• Kilakos, Kyriakos; Reed, Bruce (1993). „Ułamkowe kolorowanie wykresów całkowitych”. Kombinatoryka . 13 (4): 435–440. doi : 10.1007/BF01303515 .
• Molloy, Michael; Reed, Bruce (1998). „Wiązanie na całkowitej liczbie chromatycznej”. Kombinatoryka . 18 (2): 241-280. doi : 10.1007/PL00009820 . hdl : 1807/9465 .