Clique-width
In graph theory, the clique-width of a graph is the minimum number of labels needed to construct by means of the following 4 operations :
- Creation of a new vertex v with label i ( noted i(v) )
- Disjoint union of two labeled graphs G and H ( denoted )
- Joining by an edge every vertex labeled i to every vertex labeled j (denoted n(i,j)), where
- Renaming label i to label j ( denoted p(i,j) )
Cographs are exactly the graphs with clique-width at most 2;[1] every distance-hereditary graph has clique-width at most 3.[2] 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.[3][4] In particular, every graph property that can be expressed in MSO1 monadic second-order logic (a form of logic allowing quantification over sets of vertices) has a linear-time algorithm for graphs of bounded clique-width, by a form of Courcelle's theorem.[4]
The theory of graphs of bounded clique-width resembles that for graphs of bounded treewidth, but unlike treewidth allows for dense graphs. If a family of graphs has bounded clique-width, then either it has bounded treewidth or every complete bipartite graph is a subgraph of a graph in the family.[5] Treewidth and clique-width are also connected through the theory of line graphs: a family of graphs has bounded treewidth if and only if their line graphs have bounded clique-width.[6]
See also
Notes
References
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..