A graph-based algorithm is developed in this paper to slove the university examination timetabling problem, by transforming the classical graph model and improving the greedy algorithm. The improved algorithm can be used to meet more complicated constrain conditions in the real university credit envioronment, such as cross-major, trans-grade, minor-study and so on. The algorithm aims to slove the soft-constrain objects, which are achived by manual optimizing in the most tradition researches and cases. Firstly, the algorithm is discussed to transfer the classical graph coloring model into a clique cover problem of a weighted undirected graph. Then the greedy algorithm is impoved by the deep-first strategy, to search the solutions which satisfies both the hard-constrains and soft-constrains. The improved algorithm is proved to be better than the greedy algorithm for the solution is more reasonable, and better than the manual work for the time consumed is less. The improved algorithm can enhance the efficiency of the university timetabling, which is helpful to the academic management of our university in recent years.