3-Coloring in Time O(13289^n)
<|reference_start|>3-Coloring in Time O(13289^n): 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.<|reference_end|>
@article{beigel20003-coloring,
    title={3-Coloring in Time O(1.3289^n)},
    author={Richard Beigel and David Eppstein},
    journal={J. Algorithms 54:2 (2005) 168-204},
    year={2000},
    doi={10.1016/j.jalgor.2004.06.008},
    archivePrefix={arXiv},
    eprint={cs/0006046},
    primaryClass={cs.DS}
}