Colouring random graphs in expected polynomial time

Amin Coja-Oghlan and Anusch Taraz
Proc. 20th Symp. Theoretical Aspects of Computer Science (STACS 2003), Lecture Notes in Computer Science 2607, Helmut Alt and Michel Habib, ed., Springer-Verlag, 2003, pp. 487–498
http://www.informatik.hu-berlin.de/~taraz/paper/col.ps

Cites:

• 3-coloring in time $O(1.3446^n)$: a no-MIS algorithm
• Small maximal independent sets and faster exact graph coloring