clique-width

thumb|upright=1.35|Construction of a distance-hereditary graph of clique-width 3 by disjoint unions, relabelings, and label-joins. Vertex labels are shown as colors.

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 G \oplus H) Joining by an edge every vertex labeled to every vertex labeled (denoted by ), where Renaming label to label (denoted by )