KNOWPIA
WELCOME TO KNOWPIA

In graph theory, the **clique-width** of a graph G 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 G by means of the following 4 operations :

- Creation of a new vertex v with label i (denoted by
*i*(*v*)) - Disjoint union of two labeled graphs G and H (denoted by )
- Joining by an edge every vertex labeled i to every vertex labeled j (denoted by
*η*(*i*,*j*)), where*i*≠*j* - Renaming label i to label j (denoted by
*ρ*(*i*,*j*))

Graphs of bounded clique-width include the cographs and distance-hereditary graphs. Although it is NP-hard to compute the clique-width when it is unbounded, and unknown whether it can be computed in polynomial time when it is bounded, efficient approximation algorithms for clique-width are known. Based on these algorithms and on Courcelle's theorem, many graph optimization problems that are NP-hard for arbitrary graphs can be solved or approximated quickly on the graphs of bounded clique-width.

The construction sequences underlying the concept of clique-width were formulated by Courcelle, Engelfriet, and Rozenberg in 1990^{[1]} and by Wanke (1994). The name "clique-width" was used for a different concept by Chlebíková (1992). By 1993, the term already had its present meaning.^{[2]}

Cographs are exactly the graphs with clique-width at most 2.^{[3]}
Every distance-hereditary graph has clique-width at most 3. However, the clique-width of unit interval graphs is unbounded (based on their grid structure).^{[4]}
Similarly, the clique-width of bipartite permutation graphs is unbounded (based on similar grid structure).^{[5]}
Based on the characterization of cographs as the graphs with no induced subgraph isomorphic to a path with four vertices, the clique-width of many graph classes defined by forbidden induced subgraphs has been classified.^{[6]}

Other graphs with bounded clique-width include the k-leaf powers for bounded values of k; these are the induced subgraphs of the leaves of a tree T in the graph power *T*^{k}. However, leaf powers with unbounded exponents do not have bounded clique-width.^{[7]}

Courcelle & Olariu (2000) and Corneil & Rotics (2005) proved the following bounds on the clique-width of certain graphs:

- If a graph has clique-width at most k, then so does every induced subgraph of the graph.
^{[8]} - The complement graph of a graph of clique-width k has clique-width at most 2
*k*.^{[9]} - The graphs of treewidth w have clique-width at most 3 · 2
^{w − 1}. The exponential dependence in this bound is necessary: there exist graphs whose clique-width is exponentially larger than their treewidth.^{[10]}In the other direction, graphs of bounded clique-width can have unbounded treewidth; for instance, n-vertex complete graphs have clique-width 2 but treewidth*n*− 1. However, graphs of clique-width k that have no complete bipartite graph*K*_{t,t}as a subgraph have treewidth at most 3*k*(*t*− 1) − 1. Therefore, for every family of sparse graphs, having bounded treewidth is equivalent to having bounded clique-width.^{[11]} - Another graph parameter, the rank-width, is bounded in both directions by the clique-width: rank-width ≤ clique-width ≤ 2
^{rank-width + 1}.^{[12]}

Additionally, if a graph G has clique-width k, then the graph power *G*^{c} has clique-width at most 2*kc*^{k}.^{[13]} Although there is an exponential gap in both the bound for clique-width from treewidth and the bound for clique-width of graph powers, these bounds do not compound each other:
if a graph G has treewidth w, then *G*^{c} has clique-width at most 2(*c* + 1)^{w + 1} − 2, only singly exponential in the treewidth.^{[14]}

Can graphs of bounded clique-width be recognized in polynomial time?

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, when a construction sequence for these graphs is known.^{[15]}^{[16]} In particular, every graph property that can be expressed in MSO_{1} 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.^{[16]}

It is also possible to find optimal graph colorings or Hamiltonian cycles for graphs of bounded clique-width in polynomial time, when a construction sequence is known, but the exponent of the polynomial increases with the clique-width, and evidence from computational complexity theory shows that this dependence is likely to be necessary.^{[17]}
The graphs of bounded clique-width are χ-bounded, meaning that their chromatic number is at most a function of the size of their largest clique.^{[18]}

The graphs of clique-width three can be recognized, and a construction sequence found for them, in polynomial time using an algorithm based on split decomposition.^{[19]}
For graphs of unbounded clique-width, it is NP-hard to compute the clique-width exactly, and also NP-hard to obtain an approximation with sublinear additive error.^{[20]} However, when the clique-width is bounded, it is possible to obtain a construction sequence of bounded width (exponentially larger than the actual clique-width) in polynomial time,^{[21]} in particular in quadratic time in the number of vertices.^{[22]} It remains open whether the exact clique-width, or a tighter approximation to it, can be calculated in fixed-parameter tractable time, whether it can be calculated in polynomial time for every fixed bound on the clique-width, or even whether the graphs of clique-width four can be recognized in polynomial time.^{[20]}

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.^{[11]} 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.^{[23]}

The graphs of bounded clique-width also have bounded twin-width.^{[24]}

**^**Courcelle, Engelfriet & Rozenberg (1993).**^**Courcelle (1993).**^**Courcelle & Olariu (2000).**^**Golumbic & Rotics (2000).**^**Brandstädt & Lozin (2003).**^**Brandstädt et al. (2005); Brandstädt et al. (2006).**^**Brandstädt & Hundt (2008); Gurski & Wanke (2009).**^**Courcelle & Olariu (2000), Corollary 3.3.**^**Courcelle & Olariu (2000), Theorem 4.1.**^**Corneil & Rotics (2005), strengthening Courcelle & Olariu (2000), Theorem 5.5.- ^
^{a}^{b}Gurski & Wanke (2000). **^**Oum & Seymour (2006).**^**Todinca (2003).**^**Gurski & Wanke (2009).**^**Cogis & Thierry (2005).- ^
^{a}^{b}Courcelle, Makowsky & Rotics (2000). **^**Fomin et al. (2010).**^**Dvořák & Král' (2012).**^**Corneil et al. (2012).- ^
^{a}^{b}Fellows et al. (2009). **^**Oum & Seymour (2006); Hliněný & Oum (2008); Oum (2008); Fomin & Korhonen (2022).**^**Fomin & Korhonen (2022).**^**Gurski & Wanke (2007).**^**Bonnet et al. (2022).

- Bonnet, Édouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width I: Tractable FO model checking",
*Journal of the ACM*,**69**(1): A3:1–A3:46, arXiv:2004.14789, doi:10.1145/3486655, MR 4402362 - Brandstädt, A.; Dragan, F.F.; Le, H.-O.; Mosca, R. (2005), "New graph classes of bounded clique-width",
*Theory of Computing Systems*,**38**(5): 623–645, CiteSeerX 10.1.1.3.5994, doi:10.1007/s00224-004-1154-6, S2CID 2309695. - Brandstädt, A.; Engelfriet, J.; Le, H.-O.; Lozin, V.V. (2006), "Clique-width for 4-vertex forbidden subgraphs",
*Theory of Computing Systems*,**39**(4): 561–590, doi:10.1007/s00224-005-1199-1, S2CID 20050455. - Brandstädt, Andreas; Hundt, Christian (2008), "Ptolemaic graphs and interval graphs are leaf powers",
*LATIN 2008: Theoretical informatics*, Lecture Notes in Comput. Sci., vol. 4957, Springer, Berlin, pp. 479–491, doi:10.1007/978-3-540-78773-0_42, MR 2472761. - Brandstädt, A.; Lozin, V.V. (2003), "On the linear structure and clique-width of bipartite permutation graphs",
*Ars Combinatoria*,**67**: 273–281, CiteSeerX 10.1.1.16.2000. - Chlebíková, J. (1992), "On the tree-width of a graph",
*Acta Mathematica Universitatis Comenianae*, New Series,**61**(2): 225–236, CiteSeerX 10.1.1.30.3900, MR 1205875. - 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. - Corneil, Derek G.; Habib, Michel; Lanlignel, Jean-Marc; Reed, Bruce; Rotics, Udi (2012), "Polynomial-time recognition of clique-width ≤ 3 graphs",
*Discrete Applied Mathematics*,**160**(6): 834–865, doi:10.1016/j.dam.2011.03.020, MR 2901093. - Corneil, Derek G.; Rotics, Udi (2005), "On the relationship between clique-width and treewidth",
*SIAM Journal on Computing*,**34**(4): 825–847, doi:10.1137/S0097539701385351, MR 2148860. - Courcelle, Bruno; Engelfriet, Joost; Rozenberg, Grzegorz (1993), "Handle-rewriting hypergraph grammars",
*Journal of Computer and System Sciences*,**46**(2): 218–270, doi:10.1016/0022-0000(93)90004-G, MR 1217156. Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), MR1431281. - Courcelle, B. (1993), "Monadic second-order logic and hypergraph orientation",
*Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science (LICS '93)*, pp. 179–190, doi:10.1109/LICS.1993.287589, S2CID 39254668. - 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, CiteSeerX 10.1.1.414.1845, doi:10.1007/s002249910009, S2CID 15402031. - 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. - Dvořák, Zdeněk; Král', Daniel (2012), "Classes of graphs with small rank decompositions are χ-bounded",
*Electronic Journal of Combinatorics*,**33**(4): 679–683, arXiv:1107.2161, doi:10.1016/j.ejc.2011.12.005, S2CID 5530520 - Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), "Clique-width is NP-complete",
*SIAM Journal on Discrete Mathematics*,**23**(2): 909–939, doi:10.1137/070687256, MR 2519936. - Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket (2010), "Intractability of clique-width parameterizations",
*SIAM Journal on Computing*,**39**(5): 1941–1956, CiteSeerX 10.1.1.220.1712, doi:10.1137/080742270, MR 2592039. - Fomin, Fedor V.; Korhonen, Tuukka (2022), "Fast FPT-approximation of branchwidth",
*Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing*, ACM, pp. 886–899, arXiv:2111.03492, doi:10.1145/3519935.3519996, S2CID 243832882. - 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*", in Brandes, Ulrik; Wagner, Dorothea (eds.),_{n,n}*Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Germany, June 15–17, 2000, Proceedings*, Lecture Notes in Computer Science, vol. 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. - Gurski, Frank; Wanke, Egon (2009), "The NLC-width and clique-width for powers of graphs of bounded tree-width",
*Discrete Applied Mathematics*,**157**(4): 583–595, doi:10.1016/j.dam.2008.08.031, MR 2499471. - Hliněný, Petr; Oum, Sang-il (2008), "Finding branch-decompositions and rank-decompositions",
*SIAM Journal on Computing*,**38**(3): 1012–1032, CiteSeerX 10.1.1.94.2272, doi:10.1137/070685920, MR 2421076. - Oum, Sang-il; Seymour, Paul (2006), "Approximating clique-width and branch-width",
*Journal of Combinatorial Theory*, Series B,**96**(4): 514–528, doi:10.1016/j.jctb.2005.10.006, MR 2232389. - Oum, Sang-il (2008), "Approximating rank-width and clique-width quickly",
*ACM Transactions on Algorithms*,**5**(1): Art. 10, 20, CiteSeerX 10.1.1.574.8156, doi:10.1145/1435375.1435385, MR 2479181. - Todinca, Ioan (2003), "Coloring powers of graphs of bounded clique-width",
*Graph-theoretic concepts in computer science*, Lecture Notes in Comput. Sci., vol. 2880, Springer, Berlin, pp. 370–382, doi:10.1007/978-3-540-39890-5_32, MR 2080095. - Wanke, Egon (1994), "k-NLC graphs and polynomial algorithms",
*Discrete Applied Mathematics*,**54**(2–3): 251–266, doi:10.1016/0166-218X(94)90026-4, MR 1300250.