- 3-Coloring in time O(1.3446n): a no-MIS algorithm.
R. Beigel and D. Eppstein.
Tech. Rep. 95-033, Electronic Coll. Computational Complexity, 1995.
36th IEEE Symp. Foundations of Comp. Sci., 1995, pp. 444–453.
DIMACS Worksh. Faster Exact Solutions for NP-Hard Problems, 2000.Speeds up 3-coloring by solving a harder problem: constraint satisfaction in which each variable can take on one of three values and each constraint forbids a pair of variable assignments. The detailed solution involves several long hairy case analyses. Similar methods apply also to 3-list-coloring, 3-edge-coloring, and 3-SAT. The 3-SAT algorithm is fixed-parameter tractible in that it is polynomial time when the number of 3-variable clauses is O(log n). Merged into 3-coloring in time O(1.3289^n) for the journal version.
(DIMACS abstract and slides)