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

Cographs are exactly the graphs with clique-width at most 2;^[1] every distance-hereditary graph has clique-width at most 3 while the clique-width of unit interval graphs is unbounded (based on their grid structure).^[2] Similarly, the clique-width of bipartite permutation graphs is unbounded (based on similar grid structure).^[3] Based on the characterization of cographs as the graphs without induced subgraph isomorphic to a chordless path with four vertices, the clique-width of many graph classes defined by forbidden induced subgraphs is classified.,^[4][5] 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.^[6][7] In particular, every graph property that can be expressed in MSO₁ 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.^[7]

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.^[8] 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.^[9]

See also

• Branch-width
• Rank-width

Notes

1. Courcelle & Olariu (2000).
2. Golumbic & Rotics (2000).
3. Brandstädt & Lozin (2003).
4. Brandstädt et al. (2005).
5. Brandstädt et al. (2006).
6. Cogis & Thierry (2005).
7. Courcelle, Makowsky & Rotics (2000).
8. Gurski & Wanke (2000).
9. Gurski & Wanke (2007).

References

• Brandstädt, A.; Dragan, F.F.; Le, H.-O.; Mosca, R. (2005), "New graph classes of bounded clique-width", Theory Comput. Systems 38: 623–645, doi:10.1007/s00224-004-1154-6.
• Brandstädt, A.; Engelfriet, J.; Le, H.-O.; Lozin, V.V. (2006), "Clique-width for 4-vertex forbidden subgraphs", Theory Comput. Systems 39: 561–590, doi:10.1007/s00224-005-1199-1.
• Brandstädt, A.; Lozin, V.V. (2003), "On the linear structure and clique-width of bipartite permutation graphs", Ars Combinatoria 67: 273–281.
• 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 K_n,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.
• Gurski, Frank; Wanke, Egon (2007), "Line graphs of bounded clique-width", Discrete Mathematics 307 (22): 2734–2754, doi:10.1016/j.disc.2007.01.020.