Let G=(V,E) be a graph where V is a set of vertices and E is a set of edges. A kcoloring of G is a partition of V into k sets {V 1 , …, V k }, such that no two vertices in the same set are adjacent, i.e., if v, w belong to V i , 1 i k, then (v, w) not belong to E. The sets {V 1 , …, V k } are referred to as colors. The chromatic number, x(G), is defined as the minimum k for which G is k-colorable. The Graph k-Colorability Problem (GCP) can be stated as follows. Given a graph G, find x(G) and the corresponding coloring. GCP is a NP-hard problem [1].

GCP is very important because it has many applications; some of them are planning and scheduling problems [2] [3], timetabling [4], map coloring [5] and many others. Since GCP is a NP-hard problem, until now there are not known deterministic methods that can solved it in a polynomial time [1]. So non-deterministic algorithms have been built to solve it; one of them is Simulated Annealing (SA) [6] that has been used on GCP with good results [7] [8]. However, SA is not a complete algorithm and it not always gets the optimal solution.

The approach used in this paper is to transform GCP into a Satisfiability Problem (or SAT problem) [12] and then use the algorithm proposed in this paper. We propose to use iteratively the Threshold Accepting (TA) algorithm (a variant of Simulated Annealing) [9] and then a Davis and Putnam algorithm [10].

Simulated annealing (SA) [6] is a stochastic computational technique derived from statistical mechanics to find near global-minimum-cost solutions to large optimization problems. In many instances, finding the global minimum value of an objective function with many degrees of freedom subject to conflicting constraints is an NPcomplete problem, since the objective function will tend to have many local minimums. A procedure for solving optimization problems of this type should sample the search space in such a way that it has a high probability of finding the optimal or a near-optimal solution in a reasonable time. Over the past decade, SA has proven to be a powerful technique that meets these criteria for a wide range of problems. SA exploits an analogy between the way a metal cool and freezes into a minimum energy crystalline structure (the annealing process) and the search for a minimum in a more general system. SA makes a random search which not only accepts changes that increase its cost function f, but also some that decrease it. For this reason, SA uses a control parameter c, which by analogy with the original application is known as the "System Temperature", c starts out high and gradually decreases.

A deteriorating random move from solution S i to S j is accepted with a probability exp -(f(S j )-f(S i ))/c . If this move is not deteriorating (the new solution S j is better than the previous one S i ) then it is accepted and a new random move is proposed again. When the temperature is high, a bad move can be accepted. As c tends to zero, SA becomes more demanding through accept just better moves. The algorithm for minimization is shown below:

The INITIALIZE function starts the initial solution S i and the initial temperature c. The PERTURBATION function makes a random perturbation from S i to generate a neighborhood solution S j . The COST function gets the cost from a solution. The INC_COST function gets the difference in cost between S j and S i . Finally, the COOLING function decreases the actual temperature parameter c.

A variant of Simulated Annealing (SA) is the Threshold Accepting method (TA). It was designed by Dueck & Scheuer [9] in order to get a more efficient algorithm than Simulated Annealing. The principal difference, between SA and TA, is the mechanism of accepting the solution randomly chosen from the set of neighbors of the current solution. While SA uses a probabilistic model (see equation ( 1)), TA uses a static model: if the difference between the cost values of the chosen solution S j and the current one S i is smaller than a threshold T (or temperature), TA accepts moving to the chosen solution. Otherwise it stays at the current solution. Again, the threshold parameter T is a positive control parameter which decreases with increasing number of iterations and converges to value near to 0. Henceforth, in every iteration some solution deterioration are allowed; this deterioration depends on the current threshold T (see equation ( 2)); in this way only improving solutions with almost none deterioration solution are accepted at the end of the process.

COST(S j ) < COST(S i ) +T  accept S j (2) For SAT problems, using a good tune method Threshold Accepting yields better results than Simulated Annealing. This could be because TA does not compute the probabilistic function (1) and does not expend a lot of time making random decisions. The Threshold Accepting algorithm for minimization is the following:

Here, the DECREASE_THRESHOLD function is equivalent to the COOLING function in SA and the threshold T is named "temperature" in order to make more evident that TA belongs to Simulated Annealing Like Algorithms class (SALA). SALA uses Simulated-annealing approach with two main loops: internal loop named Metropolis Cycle and external loop called Temperature Cycle. Number of iterations in internal and external loop usually are tuned experimentally [6], [9]. However, recently an analytical method using a Markov model was proposed to tune TA solving SAT problems.

External loop executed from a initial temperature T i until a final temperature T f and the internal loop builds a Markov chain of length L k which depends on the temperature value T k (k represents the sequence index in Temperature cycle). A strong relation exists between T k and L k in a way that:

Due to TA is applied through a neighborhood structure, V, (PERTURBATION function makes a random perturbation from S i to generate a neighborhood solution S j ), the maximum number of different solutions that can be rejected from S i is the size of its neighborhoods, |V Si |. Then the maximum length of a Markov chain in a TA algorithm is the number of samples that must be taken in order to evaluate an expected fraction of different solutions from V Si at the final temperature T f , this is:

where C varies from 1 C 4.6 (exploration from 63% until 99%), L f is the length of the Markov chain at T f . From (3), L k must be incremented in a similar but inverse way that T k is decremented. Then for the geometric reduction cooling function used by Kirkpartick [6] , and Dueck and Scheuer [9],

the incremental Markov chain function must be:

where

Here, L i is the length of the Markov chain at T i , usually L i = 1, and n is the number of temperature steps from T i to T f through (5).

Now, the maximum and minimum cost increment produced through the neighborhood structure are:

for all S j V Si , and for all S i S Then T i and T f must be calculated as:

This way of determining the initial temperature enable TA to accept any possible transition at the beginning of the process, since T i is set as the maximum deterioration in cost that may be produced through the neighborhood structure. Similarly, T f enables TA to have control of the climbing probability until the algorithm performs a greedy local search.

Satisfiablity Problem [12] (or SAT) is very important in complexity theory.

Let be a propositional formula like formula (12):

where every F i is a disjunction.

Every F i is a disjunction of propositional formulas such as X 1 v X 2 v..v X r . Every F i is a clause and every X j is a literal. Every literal can take a truth value (0 or false, 1 or truth). In Satisfiability problem a set of values for the literals should be found, in such a way that the evaluation of (12) be true; otherwise if (12) is not true, we say that F is unsatisfiable. Besides we say that ( 12) is in Conjunctive Normal Form or CNF.

The Davis & Putnam method is widely regarded as one of the best deterministic methods for deciding the satisfiability [12] of a set of propositional clauses [10]. It is also a complete resolution method. This procedure calls itself after rewriting the input formula according to a number of rules for generating a smaller formula with the same truth value. The rules used for the Davis & Putnam method are: Rule 1: if the input formula has no clauses, then it is satisfiable Rule 2: if it has a clause with no literals, it is unsatisfiable Rule 3:if it has a clause with exactly one literal, then make the literal true and rewrite the formula accordingly Rule 4:if some variable appear only positively or negatively, then pick one such variable and assign a value to it to make the literal true, and rewrite the formula accordingly

If none rule could be applied, one picks up an arbitrary variable as a branching point and two new formulas are derived by assigning 0 and 1 to this variable. If one of the calls returns with the positive answer the input is satisfiable; otherwise, it is unsatisfiable.

2) To avoid the fact that a node has more that one color, add the formula X ij ~X ik 3) In order to be sure that two nodes (V i ,V j ) connected with an arc have different colors, add a clause such that if V i has color k, V j should not be color with this color. This clause is writing as X ik ~X jk . 4) In order to know which nodes are connected with an edge, an adjacent matrix A of the graph is needed; its elements are:

The reduction of a graph to the Conjunctive Normal Form (CNF) generates so many clauses even for small graphs. For example, for a full graph with 7 nodes (42 edges), 308 clauses with 98 literals can be generated. If we use Davis & Putnam algorithm to color a graph, we could start coloring with R colors (the graph's degree or from a number given). If it is not possible to color it, then we can increase R and try again.

Due to find a large chromatic number x(G) is a very hard task for a complete method as Davis & Putnam (it demands many resources), we need an incomplete method to help in this task. For this reason we have chosen the Threshold Accepting method. TA will search the chromatic number, but as it is known TA not always get the optimal solution. By this reason, the number found by TA is send to a Davis & Putnam procedure, and this one will get the optimal solution. The complete process is shown in the figure 2.

Any graph can be colored with Gmax+1 colors, where Gmax represents the graph degree. For this reason, TA will try coloring with Gmax colors. If TA gets a success, then TA will try to color with Gmax-1, and so on. When TA finishes, it sends to the output the minimum k of colors founded. In other case, when TA can not color with Gmax colors, then it will send k=Gmax+1 to Davis & Putnam procedure.

Davis & Putnam will attempt to decrease the value of k through binary partitions. The first attempt, Davis & Putnam will choose the number of colors given by (1+k)/2. If the coloring is right, it will color with (1+(1+k)/2)/2 colors, i.e., the left half. Otherwise, the algorithm will color with ((1+k)/2+k)/2 colors, the right half. This process continues until Davis & Putnam cannot decrease k. So, the chromatic number was found. This situation is shown in figure 2.

The figure 3 shows an example where TA found the number nine as its better solution and it is send to Davis & Putnam procedure. When Davis & Putnam takes the last TA solution, using binary partitions and other rules the optimal solution is waited. For example in the case of the figure 3, if Davis & Putnam can not color with five colors, it moves to other alternative, trying with seven colors. Finally, in the last partition, i.e. (7+9)/2, can not color the graph and so the result is a chromatic number equal to nine.

In this paper we presented an algorithm based on Threshold Accepting and Davis & Putnam, to solve the Graph k-Colorability Problem. Because this problem is an NPhard problem there is not a known deterministic efficient (polinomial) method. Nondeterministic methods are in general more efficient but an optimal solution is not guarantee. This method is a new alternative that promises to be more efficient that the previous ones. The main contributions of this paper are enumerated below. 1) We proposed a way to transform the graph k-colorability problem into a satisfiability problem. 2) In order to solve the former problem we proposed a new approach which makes use of the threshold accepting and Davis & Putnam algorithms. 3) The resulting algorithm is complete and using it we can get better results that the wellknown simulated annealing algorithm.