Abstract
We present a polynomial algorithm for recognizing whether a graph is perfect, thus settling a long standing open question. The algorithm uses a decomposition theorem of Conforti, Cornuéjols and Vu?sković. Another polynomial algorithm for recognizing perfect graphs, which does not use decomposition, was obtained simultaneously by Chudnovsky and Seymour. Both algorithms need a first phase developed jointly by Chudnovsky, Cornuéjols, Liu, Seymour and Vu?sković.