摘要: We consider worst case time bounds for NP-complete problems including 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a common generalization of these problems, called symbol-system satisfiability or, briefly, SSS. 3-SAT is equivalent to (2,3)-SSS while the other above special cases (3,2)-SSS; there also natural duality transformation from (a,b)-SSS (b,a)-SSS. give fast algorithm (3,2)-SSS use it improve solving listed above.
acm.org 
sci-hub.se 参考文章(12)
Bjarne Toft, Tommy R Jensen, Graph Coloring Problems ,(1994)
Ingo Schiermeyer, Solving 3-satisfiability in less than 1, 579n steps Computer Science Logic. pp. 379- 394 ,(1993) , 10.1007/3-540-56992-8_22
Ingo Schiermeyer, Deciding 3-Colourability in Less Than O(1.415^n) Steps workshop on graph theoretic concepts in computer science. pp. 177- 188 ,(1993) , 10.1007/3-540-57899-4_51
Tang Jian, An O(2 0.304n ) Algorithm for Solving Maximum Independent Set Problem IEEE Transactions on Computers. ,vol. 35, pp. 847- 851 ,(1986) , 10.1109/TC.1986.1676847
Miklo Shindo, Etsuji Tomita, A Simple Algorithm for Finding a Maximum Clique and Its Worst-Case Time Complexity Systems and Computers in Japan. ,vol. 21, pp. 1- 13 ,(1990) , 10.1002/SCJ.4690210301
E. Ya. Dantsin, Two systems for proving tautologies, based on the split method Journal of Mathematical Sciences. ,vol. 22, pp. 1293- 1305 ,(1983) , 10.1007/BF01084392
E.L. Lawler, A note on the complexity of the chromatic number problem Information Processing Letters. ,vol. 5, pp. 66- 67 ,(1976) , 10.1016/0020-0190(76)90065-X
Mihalis Yannakakis, Christos H. Papadimitriou, David S. Johnson, On generating all maximal independent sets Information Processing Letters. ,vol. 27, pp. 119- 123 ,(1988) , 10.1016/0020-0190(88)90065-8
J. W. Moon, L. Moser, On cliques in graphs Israel Journal of Mathematics. ,vol. 3, pp. 23- 28 ,(1965) , 10.1007/BF02760024
B. Monien, E. Speckenmeyer, Solving satisfiability in less than 2n steps Discrete Applied Mathematics. ,vol. 10, pp. 287- 295 ,(1985) , 10.1016/0166-218X(85)90050-2