We present the first polynomial-time combinatorial algorithm for coloring perfect graphs. At its core, our algorithm decides whether a perfect graph has a clique of a given size by counting walks on certain weighted graphs constructed from the original graph. We prove the correctness of our algorithm using a Lyapunov function argument. Joint work with Amir Ali Ahmadi (Princeton, ORFE) and Pravesh Kothari (Princeton, COS).