Before revision:  3-coloring can be solved in O( 1.4 ^n) time (Beigel and Eppstein, 2005) and 4-coloring can be solved in O( 1.8 ^n) time (Fomin, Gaspers and Saurabh, 2007).
After revision:  3-coloring can be solved in O( 1.4 ^n) time (Beigel and Eppstein, 2005) and 4-coloring can be solved in O( 1.73 ^n) time (Fomin, Gaspers and Saurabh, 2007).