Clique-width
In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of labels needed to construct by means of the following 4 operations : Creation of a new vertex with label (denoted by ) Disjoint union of two labeled graphs and (denoted by ) Joining by an edge every vertex labeled to every vertex labeled (denoted by ), where Renaming label to label (denoted by ) Graphs of bounded clique-width include the cographs and distance-hereditary graphs. Although it is NP-hard to compute the clique-width when it is unbounded, and unknown whether it can be computed in polynomial time when it is bounded, efficient approximation algorithms for clique-width are known. Based on these algorithms and on Courcelle's theorem, many graph optimization problems that are NP-hard for arbitrary graphs can be solved or approximated quickly on the graphs of bounded clique-width. The construction sequences underlying the concept of clique-width were formulated by Courcelle, Engelfriet, and Rozenberg in 1990 and by . The name "clique-width" was used for a different concept by . By 1993, the term already had its present meaning. Special classes of graphs Cographs are exactly the graphs with clique-width at most 2. Every distance-hereditary graph has clique-width at most 3. However, the clique-width of unit interval graphs is unbounded (based on their grid structure). Similarly, the clique-width of bipartite permutation graphs is unbounded (based on similar grid structure). Based on the characterization of cographs as the graphs with no induced subgraph isomorphic to a path with four vertices, the clique-width of many graph classes defined by forbidden induced subgraphs has been classified. Other graphs with bounded clique-width include the -leaf powers for bounded values of ; these are the induced subgraphs of the leaves of a tree in the graph power . However, leaf powers with unbounded exponents do not have bounded clique-width. Bounds and proved the following bounds on the clique-width of certain graphs: If a graph has clique-width at most , then so does every induced subgraph of the graph. The complement graph of a graph of clique-width has clique-width at most . The graphs of treewidth have clique-width at most . The exponential dependence in this bound is necessary: there exist graphs whose clique-width is exponentially larger than their treewidth. In the other direction, graphs of bounded clique-width can have unbounded treewidth; for instance, -vertex complete graphs have clique-width 2 but treewidth . However, graphs of clique-width that have no complete bipartite graph as a subgraph have treewidth at most . Therefore, for every family of sparse graphs, having bounded treewidth is equivalent to having bounded clique-width. Another graph parameter, the rank-width, is bounded in both directions by the clique-width: Additionally, if a graph has clique-width , then the graph power has clique-width at most . Although there is an exponential gap in both the