The AFISA procedure improves the current coloring by successively changing the color of a vertex in the search space \(\mathcal {S}_k\)  (with a maximum of \(k\)  colors). Such a change is called an one-move. To prevent the search from revisiting already visited colorings, a vertex cannot change its color for the next \(tt\)  (called tabu tenure) iterationsIn the original AFISA algorithm, the tabu tenure concerns past moves (as in the original TabuCol algorithm [1]}) instead of completely freezing a vertex. However we empirically observed that it is more effective to freeze a vertex that has just changed its color in order to avoid too much color changes of the same vertex without any improvement of the score (plateau).. The tabu tenure is set to be \(L + 0.2 \times |V|\) , where \(L\)  is a random integer from \([0;9]\)  and \(|V|\)  is the number of vertices in the graph.
