3-kolorowanie grafów w czasie wielomianowym

Poprawnym kolorowaniem grafu nazywamy funkcję, która przyporządkowuje każdemu wierzchołkowi pewien kolor w ten sposób, że żadne dwa sąsiadujące wierzchołki nie są tak samo pokolorowane. W przypadku ogólnym jest to problem NP-zupełny. Na początku prezentujemy kilka metod często używanych w algorytmach do 3-kolorowania:redukcję diamentów i rozdeństw, kolorowanie wierzchołków w określonej kolejności za pomocą algorytmu First-Fit oraz konwersję do problemu kolorowania z list długości 2. W kolejnych sekcjach opisujemy kilka ciekawych klas grafów dla których instnieją wielomianowe algorytmy rozwiązujące problem 3-kolorowania. Pierwszą klasą którą prezentujemy są grafy z dużym minimalnym stopniem wierzchołka. Pokazujemy jak znaleźć ich 3-kolorowanie posługując się odpowiednio małym zbiorem dominującym. Kolejną rozważaną klasą są grafy bez asteroidalnych trójek (AT-free). Pokazujemy jak znaleźć dla nich poprawne kolorowanie przez redukcję diamentów, dekompozyję wynikowego grafu i redukcji minimalnych separatorów niezależnych. Rozważamy również klasę grafów lokalnie spójnych. Dla tych grafów poprawne rozwiązanie może zostać osiągnięte przez pokolorowanie pary sąsiadujących wierzchołków, a później reszty, w pewnej określonej kolejności. Następna klasa, grafy beta-doskonałę, ma wielomianowy algorytm znajdywania minimalnego poprawnego kolorowania. Oczywiście może on zostać użyty również dla 3-kolorowania. Ostatnimi analizowanymi grafami są te o średnicy dwa oraz rozspójniającym sąsiedztwie. Mogą być 3-kolorowane przez prostą konwersję do problemu kolorowania z list długości 2.

A proper graph coloring is a function which gives each vertex such color that there is no pair of adjacent vertices colored in the same way. In general the problem of coloring graphs with three colors is NP-complete. In the beginning of the following article we present some methods typically used in algorithms for 3-coloring: reduction of diamonds and siblings, coloring vertices in a certain order with First-Fit and solving some instances by conversion to 2-list-coloring problem. In the next sections we describe some interesting graph classes for which there exist a polynomial time algorithms for solving 3-coloring problem. The first class we present are graphs with a high minimal vertex degree. We show how to color them with three colors by finding a small dominating set. The next class which we consider graphs without asteroidal triples (AT-free). We show how to find their proper coloring by reducing diamonds, decomposing the resulting graph into blocks and then merging its minimal stable separators.We also consider a class of locally connected graphs. For these graphs a proper solution can be obtained by coloring a pair of adjacent vertices and then the rest of vertices in a certain order. The next class, beta-perfect graphs, has polynomial time algorithm for finding minimal proper coloring. Clearly it can be used for 3-coloring as well. Finally we analyze graphs with diameter two and articulation neighborhood. They can be 3-colored by a simple conversion to 2-list-coloring instance.