Rozszerzenie do wstępnego kolorowania

W teorii grafów rozszerzenie wstępnego kolorowania to problem rozszerzenia kolorowania grafu podzbioru wierzchołków grafu przy danym zestawie kolorów na kolorowanie całego grafu, które nie przypisuje tego samego koloru żadnym dwóm sąsiednim wierzchołkom .

Złożoność

Rozszerzenie Precoloring ma zwykły problem z kolorowaniem grafów jako szczególny przypadek, w którym początkowo pokolorowany podzbiór wierzchołków jest pusty; dlatego jest NP-zupełny . Jednak jest on również NP-zupełny dla niektórych innych klas grafów, na których zwykły problem kolorowania grafów jest łatwiejszy. Na przykład jest to NP-zupełne na wykresach wieży , dla czego odpowiada problemowi uzupełnienia częściowo wypełnionego kwadratu łacińskiego .

Problem można rozwiązać w czasie wielomianowym dla wykresów o ograniczonej szerokości drzewa , ale wykładnik wielomianu zależy od szerokości drzewa. Można to rozwiązać w czasie liniowym dla instancji rozszerzenia wstępnego kolorowania, w których zarówno liczba kolorów, jak i szerokość drzewa są ograniczone.

Powiązane problemy

Rozszerzenie wstępnego kolorowania można postrzegać jako szczególny przypadek kolorowania listowego , czyli problemu kolorowania grafu, w którym nie pokolorowano żadnych wierzchołków, ale każdy wierzchołek ma przypisaną listę dostępnych kolorów. Aby przekształcić problem rozszerzenia wstępnego kolorowania w problem kolorowania listowego, przypisz każdemu niepokolorowanemu wierzchołkowi w problemie rozszerzenia wstępnego kolorowania listę kolorów, które nie zostały jeszcze użyte przez jego początkowo pokolorowanych sąsiadów, a następnie usuń kolorowe wierzchołki z grafu.

Sudoku można modelować matematycznie jako przykłady problemu rozszerzenia wstępnego kolorowania na wykresach Sudoku .

Linki zewnętrzne

• Bibliografia na temat rozszerzenia wstępnego kolorowania , Dániel Marx