We will discuss the Beigel-Eppstein 3-coloring algorithm,
which is based on the symbol system problem and runs in time 1.35^n.
Unlike previous algorithms, our algorithm is not based on maximal
independent sets.
Then we will discuss a new recursive algorithm for the maximum
independent set problem. This algorithm runs in time 1.22^n and is
the fastest polynomial space algorithm known for the problem
(improving on results of Tarjan-Trojanowski, Jian, and Robson).
Unlike previous algorithms for this problem, our algorithm may add
edges as it progresses.