An approach for decomposing a layout for triple patterning lithography is described. In one embodiment, a triple patterning conflict graph is built from a layout having pattern features specified as shapes. The triple patterning conflict graph represents the shapes in the layout and coloring constraints associated with the shapes. The shapes represented by the triple patterning conflict graph are decomposed into three colors to avoid color conflict, while balancing the color density among the three colors and minimizing a number of stitches used to represent the shapes in the layout. Color conflicts in the decomposition are resolved by selectively segmenting the shapes in the decomposition that are associated with the color conflict.