With the need of 16/11nm cells, triple patterning lithography (TPL) has been concerned in lithography industry. Based on a new conflict projection technique to identify conflicts, we formulate in this paper the TPL layout decomposition problem as a minimum cost coloring problem. The problem is solved in two steps. First, it is relaxed to a nonlinear 0-1 programming problem without considering stitch insertions. Second, legalization methods are introduced to legalize a solution of the nonlinear 0-1 programming problem into a feasible one. At the legalization step, we prior utilize one-stitch insertions to eliminate conflicts. A backtrack coloring algorithm is also used at this step to obtain a better coloring solution. At last, to improve scalability of our decomposition method, two graph reduction approaches are introduced. We test the decomposition method on the benchmarks C432-C7552 and S1488-S15850 with minimum coloring spacings 120nm and 100nm, respectively. Comparisons of experimental results show that our approach achieves optimal costs better than those by some state-of-the-art decomposers. Moreover, our decomposition method is faster than most of the decomposers on the tested benchmarks.