Definitions
Nearby Words

# Clique-width

In graph theory, the clique-width of a graph $G$ is the minimum number of labels needed to construct $G$ by means of the following 4 operations :

1. Creation of a new vertex v with label i (noted i(v) )
2. Disjoint union of two labeled graphs G and H (denoted $G oplus H$ )
3. Joining by an edge every vertex lebeled i to every vertex labeled j (denoted n(i,j))
4. Renaming label i to label j (denoted p(i,j) )

Cographs are exactly the graphs with clique-width at most 2; every distance-hereditary graph has clique-width at most 3 . Many optimization problems that are NP-hard for more general classes of graphs may be solved efficiently by dynamic programming on graphs of bounded clique-width (). The theory of graphs of bounded clique-width resembles that for graphs of bounded treewidth, but unlike treewidth allows for dense graphs.

## References

| doi = 10.1016/j.disopt.2005.03.004}}.

• .

• .

| doi = 10.1142/S0129054100000260}}.

Search another word or see Widthon Dictionary | Thesaurus |Spanish