text: We consider worst case time bounds for NP-complete problems including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a constraint satisfaction (CSP) formulation of these problems. 3-SAT is equivalent to (2,3)-CSP while the other problems above are special cases of (3,2)-CSP; there is also a natural duality transformation from (a,b)-CSP to (b,a)-CSP. We give a fast algorithm for (3,2)-CSP and use it to improve the time bounds for solving the other problems listed above. Our techniques involve a mixture of Davis-Putnam-style backtracking with more sophisticated matching and network flow based ideas.
  @cite_5: Abstract We present an algorithm that generates all maximal independent sets of a graph in lexicographic order, with only polynomial delay between the output of two successive independent sets. We also show that there is no polynomial-delay algorithm for generating all maximal independent sets in reverse lexicographic order, unless P=NP.
  @cite_15: 
  @cite_21: A clique is a maximal complete subgraph of a graph. The maximum number of cliques possible in a graph withn nodes is determined. Also, bounds are obtained for the number of different sizes of cliques possible in such a graph.
  @cite_18: In this paper we describe and analyze an improved algorithm for deciding the 3-Colourability problem. If G is a simple graph on n vertices then we will show that this algorithm tests a graph for 3-Colourability, i.e. an assignment of three colours to the vertices of G such that two adjacent vertices obtain different colours, in less than O(1.415n) steps.
summary: For three-coloring, we know of several relevant references. Lawler @cite_15 is primarily concerned with the general chromatic number, but he also gives the following very simple algorithm for 3-coloring: for each maximal independent set, test whether the complement is bipartite. The maximal independent sets can be listed with polynomial delay @cite_5 , and there are at most @math such sets @cite_21 , so this algorithm takes time @math . Schiermeyer @cite_18 gives a complicated algorithm for solving 3-colorability in time @math , based on the following idea: if there is one vertex @math of degree @math then the graph is 3-colorable iff @math is bipartite, and the problem is easily solved. Otherwise, Schiermeyer performs certain reductions involving maximal independent sets that attempt to increase the degree of @math while partitioning the problem into subproblems, at least one of which will remain solvable. Our @math bound significantly improves both of these results.