Clique width of Partner limited graphs

The clique-width of a graph G is the minimum number of labels that are required for dening G by an expression based on graph operations using vertex labels. The Partner limited graphs (PL-graphs for short) are defined to be graphs with a limited number of P4ʹs. We prove that PL-graphs are of bounded clique-width. It follows that a large number of optimization problems have polynomial solutions for this family of graphs