Grafem nazywamy obiekt złożony z wierzchołków (punktów) i – łączących niektóre z nich – krawędzi (linii). Zakładamy, że dowolne dwa wierzchołki mogą być połączone co najwyżej jedną krawędzią i że żaden wierzchołek nie jest połączony krawędzią z samym sobą. Dwa wierzchołki nazywamy sąsiednimi, jeżeli są połączone krawędzią. Na marginesie widnieje rysunek przykładowego grafu, którego zbiorem wierzchołków jest \(\{\mathtt{a},\mathtt{b},\mathtt{d},\mathtt{i},\mathtt{k},\mathtt{r},\mathtt{s},\mathtt{u},\mathtt{z}\}.\)
Rozważmy zadanie polegające na pokolorowaniu każdego wierzchołka grafu tak, aby żadne dwa sąsiednie nie miały tego samego koloru. Tak postawiony problem jest trywialny – aby spełnić przedstawiony warunek, wystarczy każdemu wierzchołkowi nadać unikatowy kolor. Co jednak, gdy chcemy użyć mniej kolorów niż mamy wierzchołków, a wręcz: możliwie jak najmniej? To zadanie jest już znacznie trudniejsze i jednym z pomocnych narzędzi jest algorytm first-fit:
Ustawmy zbiór kolorów w ciąg \((c_1,c_2,\ldots)\) – dzięki temu będziemy mogli mówić o kolorze pierwszym, drugim itd.
Oczywiście możemy przyjąć, że początkowa lista kolorów jest nieskończona, ale wystarczy się ograniczyć do liczby kolorów nie większej niż liczba wierzchołków danego grafu – poza pewnymi szczególnymi przypadkami nie użyjemy ich wszystkich!
Ustawmy zbiór wierzchołków \(\{v_1,v_2,\ldots,v_n\}\) w ciąg \((v_{\pi(1)},v_{\pi(2)},\ldots,v_{\pi(n)}).\)
Dla \(1\leqslant i\leqslant n\) kolorujemy wierzchołek \(v_{\pi(i)}\) najmniejszym dostępnym kolorem.
Zauważmy, że liczba kolorów użytych przy first-fit może zależeć od wyboru ciągu wierzchołków! Zobrazujmy to na naszym przykładowym grafie. Dany niech będzie ciąg kolorów 
Przy kolejności \((\mathtt{a},\mathtt{b},\mathtt{s},\mathtt{d},\mathtt{u},\mathtt{z},\mathtt{k},\mathtt{r},\mathtt{i})\) używamy tylko dwóch kolorów, a przy \((\mathtt{a},\mathtt{i},\mathtt{u},\mathtt{d},\mathtt{z},\mathtt{s},\mathtt{b},\mathtt{k},\mathtt{r})\) – czterech!
Oczywiście istnieją takie grafy, w których niezależnie od kolejności wierzchołków, użyjemy takiej samej liczby kolorów – poświadczyć o tym mogą chociażby gwiazdy:
A czy różnica pomiędzy najmniejszą a największą liczbą kolorów względem algorytmu first-fit może być dowolnie duża? Aby uzasadnić odpowiedź twierdzącą, posłużymy się następującą konstrukcją.
Gwiazdą nazywamy graf, w którym jedynymi krawędziami są te, które łączą jeden wyróżniony wierzchołek z pozostałymi.
Niech \(n\geqslant3.\) Rozważmy graf, którego zbiór wierzchołków składa się z dwóch równolicznych i rozłącznych podzbiorów: \(\{\mathtt{a}_1,\mathtt{a}_2,\ldots,\mathtt{a}_n\}\) oraz \(\{\mathtt{b}_1,\mathtt{b}_2,\ldots,\mathtt{b}_n\}.\) Każdy wierzchołek \(\mathtt{a}_i\) łączymy krawędzią z każdym wierzchołkiem \(\mathtt{b}_j,\) o ile \(i\neq j.\)
Zauważmy, że dla takiego grafu najmniejsza liczba kolorów użytych przez first-fit to \(2,\) a największa to \(n.\) Na marginesie prezentujemy to dla \(n=5.\)
Najmniejsza możliwa liczba kolorów uzyskana dzięki algorytmowi first-fit to tzw. liczba chromatyczna, a największa – liczba Grundy’ego danego grafu. Zachęcam do samodzielnego poszukiwania zależności między tymi dwiema wartościami!