Clique-width

From Wikipedia, the free encyclopedia

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 labeled i to every vertex labeled j (denoted n(i,j)), where i\neq j
  4. Renaming label i to label j ( denoted p(i,j) )

Cographs are exactly the graphs with clique-width at most 2 (Courcelle & Olariu 2000); every distance-hereditary graph has clique-width at most 3 (Golumbic & Rotics 2000). 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 (Cogis & Thierry 2005; Courcelle, Makowsky & Rotics 2000).

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 (Gurski & Wanke 2000).

References

  • Cogis, O.; Thierry, E. (2005), "Computing maximum stable sets for distance-hereditary graphs", Discrete Optimization 2 (2): 185–188, doi:10.1016/j.disopt.2005.03.004, MR 2155518 .
  • Courcelle, B.; Makowsky, J. A.; Rotics, U. (2000), "Linear time solvable optimization problems on graphs on bounded clique width", Theory of Computing Systems 33 (2): 125–150, doi:10.1007/s002249910009 .
  • Courcelle, B.; Olariu, S. (2000), "Upper bounds to the clique width of graphs", Discrete Applied Mathematics 101 (1–3): 77–144, doi:10.1016/S0166-218X(99)00184-5 .
  • Golumbic, Martin Charles; Rotics, Udi (2000), "On the clique-width of some perfect graph classes", International Journal of Foundations of Computer Science 11 (3): 423–443, doi:10.1142/S0129054100000260, MR 1792124 .
  • Gurski, Frank; Wanke, Egon (2000), "The tree-width of clique-width bounded graphs without Kn,n", in Brandes, Ulrik; Wagner, Dorothea, Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Germany, June 15–17, 2000, Proceedings, Lecture Notes in Computer Science 1928, Berlin: Springer, pp. 196–205, doi:10.1007/3-540-40064-8_19, MR 1850348 .
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.