The Clique Width of Two Classes of Series-Parallel Digraphs

The concept of graphs with clique-width at most was first introduced by Courcelle et al.to be the graphs that can be characterized using -expressions derived from graph operations that use labels of vertices. If the clique-width for some graph is bounded then a grand number of algorithmic problems, in general NP-hard, can be solved in polynomial time when restricted to this graph. This important fact motivated the researchers to prove that the clique-width of certain graphs is bounded. Following this research direction, we prove in this paper that the clique-width of series-parallel digraphs is at most 6 and we present an time algorithm to construct a 6-expression for this class of digraphs. In another part, we present a linear time recognition algorithm for a similar class of series-parallel digraphs and prove that the clique-width of this class is at most 3.