The Clique-width of a graph is an invariant which measures the complexity of the graph structures. A graph of bounded tree-width is also of bounded Clique-width (but not the converse). For graphs G of bounded , given the bounded width decomposition of G, every optimization, enumeration or evaluation problem that can be defined by a Monadic Second Order Logic formula using quantifiers on vertices but not on edges, can be solved in polynomial time.
This is reminiscent of the situation for graphs of bounded tree-width, where the same statement holds even if quantifiers are also allowed on edges. Thus, graphs of bounded Clique-width are a larger class than graphs of bounded tree-width, on which we can resolve fewer, but still many, optimization problems efficiently.
In this paper we present the first polynomial time algorithm (O (n 2 m)) to recognize graphs of at most 3.