# Clique-width

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Clique-width
> Markdown URL: https://mediated.wiki/source/Clique-width.md
> Source: https://en.wikipedia.org/wiki/Clique-width
> Source revision: 1244802643
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Measure of graph complexity

Construction of a [distance-hereditary graph](/source/Distance-hereditary_graph) of clique-width 3 by disjoint unions, relabelings, and label-joins. Vertex labels are shown as colors.

In [graph theory](/source/Graph_theory), the **clique-width** of a [graph](/source/Graph_(discrete_mathematics)) G is a parameter that describes the structural complexity of the graph; it is closely related to [treewidth](/source/Treewidth), but unlike treewidth it can be small for [dense graphs](/source/Dense_graph). It is defined as the minimum number of [labels](/source/Graph_labeling) needed to construct G by means of the following 4 operations :

1. Creation of a new vertex v with label i (denoted by *i*(*v*))

1. [Disjoint union](/source/Disjoint_union_of_graphs) of two labeled graphs G and H (denoted by G ⊕ H {\displaystyle G\oplus H} )

1. Joining by an edge every vertex labeled i to every vertex labeled j (denoted by *η*(*i*,*j*)), where *i* ≠ *j*

1. Renaming label i to label j (denoted by *ρ*(*i*,*j*))

Graphs of bounded clique-width include the [cographs](/source/Cograph) and [distance-hereditary graphs](/source/Distance-hereditary_graph). Although it is [NP-hard](/source/NP-hard) to compute the clique-width when it is unbounded, and unknown whether it can be computed in [polynomial time](/source/Polynomial_time) when it is bounded, efficient [approximation algorithms](/source/Approximation_algorithm) for clique-width are known. Based on these algorithms and on [Courcelle's theorem](/source/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](/source/Bruno_Courcelle), Engelfriet, and Rozenberg in 1990[1] and by [Wanke (1994)](#CITEREFWanke1994). The name "clique-width" was used for a different concept by [Chlebíková (1992)](#CITEREFChlebíková1992). By 1993, the term already had its present meaning.[2]

## Special classes of graphs

[Cographs](/source/Cograph) are exactly the graphs with clique-width at most 2.[3] Every [distance-hereditary graph](/source/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](/source/Leaf_power) for bounded values of k; these are the [induced subgraphs](/source/Induced_subgraph) of the leaves of a tree T in the [graph power](/source/Graph_power) *T**k*. However, leaf powers with unbounded exponents do not have bounded clique-width.[7]

## Bounds

[Courcelle & Olariu (2000)](#CITEREFCourcelleOlariu2000) and [Corneil & Rotics (2005)](#CITEREFCorneilRotics2005) 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](/source/Induced_subgraph) of the graph.[8]

- The [complement graph](/source/Complement_graph) of a graph of clique-width k has clique-width at most 2*k*.[9]

- The graphs of [treewidth](/source/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](/source/Complete_graph) 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](/source/Biclique-free_graph) have treewidth at most 3*k*(*t* − 1) − 1. Therefore, for every family of [sparse graphs](/source/Sparse_graph), having bounded treewidth is equivalent to having bounded clique-width.[11]

- Another graph parameter, the [rank-width](/source/Rank-width), is bounded in both directions by the clique-width: rank-width ≤ clique-width ≤ 2rank-width + 1.[12]

Additionally, if a graph G has clique-width k, then the [graph power](/source/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]

## Computational complexity

Unsolved problem in mathematics

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

[More unsolved problems in mathematics](/source/List_of_unsolved_problems_in_mathematics)

Many optimization problems that are [NP-hard](/source/NP-hard) for more general classes of graphs may be solved efficiently by [dynamic programming](/source/Dynamic_programming) on graphs of bounded clique-width, when a construction sequence for these graphs is known.[15][16] In particular, every [graph property](/source/Graph_property) that can be expressed in MSO1 [monadic second-order logic](/source/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](/source/Courcelle's_theorem).[16]

It is also possible to find optimal [graph colorings](/source/Graph_coloring) or [Hamiltonian cycles](/source/Hamiltonian_cycle) 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](/source/%CE%A7-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](/source/Split_decomposition).[19] For graphs of unbounded clique-width, it is [NP-hard](/source/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](/source/Parameterized_complexity), 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]

## Related width parameters

The theory of graphs of bounded clique-width resembles that for graphs of bounded [treewidth](/source/Treewidth), but unlike treewidth allows for [dense graphs](/source/Dense_graph). If a family of graphs has bounded clique-width, then either it has bounded treewidth or every [complete bipartite graph](/source/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](/source/Line_graph): 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](/source/Twin-width).[24]

## Notes

1. **[^](#cite_ref-FOOTNOTECourcelleEngelfrietRozenberg1993_1-0)** [Courcelle, Engelfriet & Rozenberg (1993)](#CITEREFCourcelleEngelfrietRozenberg1993).

1. **[^](#cite_ref-FOOTNOTECourcelle1993_2-0)** [Courcelle (1993)](#CITEREFCourcelle1993).

1. **[^](#cite_ref-FOOTNOTECourcelleOlariu2000_3-0)** [Courcelle & Olariu (2000)](#CITEREFCourcelleOlariu2000).

1. **[^](#cite_ref-FOOTNOTEGolumbicRotics2000_4-0)** [Golumbic & Rotics (2000)](#CITEREFGolumbicRotics2000).

1. **[^](#cite_ref-FOOTNOTEBrandstädtLozin2003_5-0)** [Brandstädt & Lozin (2003)](#CITEREFBrandstädtLozin2003).

1. **[^](#cite_ref-6)** [Brandstädt et al. (2005)](#CITEREFBrandstädtDraganLeMosca2005); [Brandstädt et al. (2006)](#CITEREFBrandstädtEngelfrietLeLozin2006).

1. **[^](#cite_ref-7)** [Brandstädt & Hundt (2008)](#CITEREFBrandstädtHundt2008); [Gurski & Wanke (2009)](#CITEREFGurskiWanke2009).

1. **[^](#cite_ref-8)** [Courcelle & Olariu (2000)](#CITEREFCourcelleOlariu2000), Corollary 3.3.

1. **[^](#cite_ref-9)** [Courcelle & Olariu (2000)](#CITEREFCourcelleOlariu2000), Theorem 4.1.

1. **[^](#cite_ref-10)** [Corneil & Rotics (2005)](#CITEREFCorneilRotics2005), strengthening [Courcelle & Olariu (2000)](#CITEREFCourcelleOlariu2000), Theorem 5.5.

1. ^ [***a***](#cite_ref-FOOTNOTEGurskiWanke2000_11-0) [***b***](#cite_ref-FOOTNOTEGurskiWanke2000_11-1) [Gurski & Wanke (2000)](#CITEREFGurskiWanke2000).

1. **[^](#cite_ref-FOOTNOTEOumSeymour2006_12-0)** [Oum & Seymour (2006)](#CITEREFOumSeymour2006).

1. **[^](#cite_ref-FOOTNOTETodinca2003_13-0)** [Todinca (2003)](#CITEREFTodinca2003).

1. **[^](#cite_ref-FOOTNOTEGurskiWanke2009_14-0)** [Gurski & Wanke (2009)](#CITEREFGurskiWanke2009).

1. **[^](#cite_ref-FOOTNOTECogisThierry2005_15-0)** [Cogis & Thierry (2005)](#CITEREFCogisThierry2005).

1. ^ [***a***](#cite_ref-FOOTNOTECourcelleMakowskyRotics2000_16-0) [***b***](#cite_ref-FOOTNOTECourcelleMakowskyRotics2000_16-1) [Courcelle, Makowsky & Rotics (2000)](#CITEREFCourcelleMakowskyRotics2000).

1. **[^](#cite_ref-FOOTNOTEFominGolovachLokshtanovSaurabh2010_17-0)** [Fomin et al. (2010)](#CITEREFFominGolovachLokshtanovSaurabh2010).

1. **[^](#cite_ref-FOOTNOTEDvořákKrál'2012_18-0)** [Dvořák & Král' (2012)](#CITEREFDvořákKrál'2012).

1. **[^](#cite_ref-FOOTNOTECorneilHabibLanlignelReed2012_19-0)** [Corneil et al. (2012)](#CITEREFCorneilHabibLanlignelReed2012).

1. ^ [***a***](#cite_ref-FOOTNOTEFellowsRosamondRoticsSzeider2009_20-0) [***b***](#cite_ref-FOOTNOTEFellowsRosamondRoticsSzeider2009_20-1) [Fellows et al. (2009)](#CITEREFFellowsRosamondRoticsSzeider2009).

1. **[^](#cite_ref-21)** [Oum & Seymour (2006)](#CITEREFOumSeymour2006); [Hliněný & Oum (2008)](#CITEREFHliněnýOum2008); [Oum (2008)](#CITEREFOum2008); [Fomin & Korhonen (2022)](#CITEREFFominKorhonen2022).

1. **[^](#cite_ref-FOOTNOTEFominKorhonen2022_22-0)** [Fomin & Korhonen (2022)](#CITEREFFominKorhonen2022).

1. **[^](#cite_ref-FOOTNOTEGurskiWanke2007_23-0)** [Gurski & Wanke (2007)](#CITEREFGurskiWanke2007).

1. **[^](#cite_ref-FOOTNOTEBonnetKimThomasséWatrigant2022_24-0)** [Bonnet et al. (2022)](#CITEREFBonnetKimThomasséWatrigant2022).

## References

- Bonnet, Édouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width I: Tractable FO model checking", *[Journal of the ACM](/source/Journal_of_the_ACM)*, **69** (1): A3:1–A3:46, [arXiv](/source/ArXiv_(identifier)):[2004.14789](https://arxiv.org/abs/2004.14789), [doi](/source/Doi_(identifier)):[10.1145/3486655](https://doi.org/10.1145%2F3486655), [MR](/source/MR_(identifier)) [4402362](https://mathscinet.ams.org/mathscinet-getitem?mr=4402362)

- [Brandstädt, A.](/source/Andreas_Brandst%C3%A4dt); 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](/source/CiteSeerX_(identifier)) [10.1.1.3.5994](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.5994), [doi](/source/Doi_(identifier)):[10.1007/s00224-004-1154-6](https://doi.org/10.1007%2Fs00224-004-1154-6), [S2CID](/source/S2CID_(identifier)) [2309695](https://api.semanticscholar.org/CorpusID:2309695).

- [Brandstädt, A.](/source/Andreas_Brandst%C3%A4dt); 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](/source/Doi_(identifier)):[10.1007/s00224-005-1199-1](https://doi.org/10.1007%2Fs00224-005-1199-1), [S2CID](/source/S2CID_(identifier)) [20050455](https://api.semanticscholar.org/CorpusID: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](/source/Doi_(identifier)):[10.1007/978-3-540-78773-0_42](https://doi.org/10.1007%2F978-3-540-78773-0_42), [MR](/source/MR_(identifier)) [2472761](https://mathscinet.ams.org/mathscinet-getitem?mr=2472761).

- [Brandstädt, A.](/source/Andreas_Brandst%C3%A4dt); Lozin, V.V. (2003), "On the linear structure and clique-width of bipartite permutation graphs", *[Ars Combinatoria](/source/Ars_Combinatoria_(journal))*, **67**: 273–281, [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.16.2000](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.2000).

- [Chlebíková, J.](/source/Janka_Chleb%C3%ADkov%C3%A1) (1992), "On the tree-width of a graph", *Acta Mathematica Universitatis Comenianae*, New Series, **61** (2): 225–236, [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.30.3900](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.3900), [MR](/source/MR_(identifier)) [1205875](https://mathscinet.ams.org/mathscinet-getitem?mr=1205875).

- Cogis, O.; Thierry, E. (2005), "Computing maximum stable sets for distance-hereditary graphs", *Discrete Optimization*, **2** (2): 185–188, [doi](/source/Doi_(identifier)):[10.1016/j.disopt.2005.03.004](https://doi.org/10.1016%2Fj.disopt.2005.03.004), [MR](/source/MR_(identifier)) [2155518](https://mathscinet.ams.org/mathscinet-getitem?mr=2155518).

- [Corneil, Derek G.](/source/Derek_Corneil); Habib, Michel; Lanlignel, Jean-Marc; [Reed, Bruce](/source/Bruce_Reed_(mathematician)); Rotics, Udi (2012), "Polynomial-time recognition of clique-width ≤ 3 graphs", *[Discrete Applied Mathematics](/source/Discrete_Applied_Mathematics)*, **160** (6): 834–865, [doi](/source/Doi_(identifier)):[10.1016/j.dam.2011.03.020](https://doi.org/10.1016%2Fj.dam.2011.03.020), [MR](/source/MR_(identifier)) [2901093](https://mathscinet.ams.org/mathscinet-getitem?mr=2901093).

- [Corneil, Derek G.](/source/Derek_Corneil); Rotics, Udi (2005), "On the relationship between clique-width and treewidth", *[SIAM Journal on Computing](/source/SIAM_Journal_on_Computing)*, **34** (4): 825–847, [doi](/source/Doi_(identifier)):[10.1137/S0097539701385351](https://doi.org/10.1137%2FS0097539701385351), [MR](/source/MR_(identifier)) [2148860](https://mathscinet.ams.org/mathscinet-getitem?mr=2148860).

- [Courcelle, Bruno](/source/Bruno_Courcelle); Engelfriet, Joost; Rozenberg, Grzegorz (1993), "Handle-rewriting hypergraph grammars", *Journal of Computer and System Sciences*, **46** (2): 218–270, [doi](/source/Doi_(identifier)):[10.1016/0022-0000(93)90004-G](https://doi.org/10.1016%2F0022-0000%2893%2990004-G), [MR](/source/MR_(identifier)) [1217156](https://mathscinet.ams.org/mathscinet-getitem?mr=1217156). Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), [MR](/source/MR_(identifier)) [1431281](https://mathscinet.ams.org/mathscinet-getitem?mr=1431281).

- [Courcelle, B.](/source/Bruno_Courcelle) (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](/source/Doi_(identifier)):[10.1109/LICS.1993.287589](https://doi.org/10.1109%2FLICS.1993.287589), [S2CID](/source/S2CID_(identifier)) [39254668](https://api.semanticscholar.org/CorpusID:39254668).

- [Courcelle, B.](/source/Bruno_Courcelle); [Makowsky, J. A.](/source/Johann_Makowsky); Rotics, U. (2000), "Linear time solvable optimization problems on graphs on bounded clique width", *Theory of Computing Systems*, **33** (2): 125–150, [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.414.1845](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.414.1845), [doi](/source/Doi_(identifier)):[10.1007/s002249910009](https://doi.org/10.1007%2Fs002249910009), [S2CID](/source/S2CID_(identifier)) [15402031](https://api.semanticscholar.org/CorpusID:15402031).

- [Courcelle, B.](/source/Bruno_Courcelle); Olariu, S. (2000), ["Upper bounds to the clique width of graphs"](https://digitalcommons.odu.edu/computerscience_fac_pubs/122), *[Discrete Applied Mathematics](/source/Discrete_Applied_Mathematics)*, **101** (1–3): 77–144, [doi](/source/Doi_(identifier)):[10.1016/S0166-218X(99)00184-5](https://doi.org/10.1016%2FS0166-218X%2899%2900184-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](/source/ArXiv_(identifier)):[1107.2161](https://arxiv.org/abs/1107.2161), [doi](/source/Doi_(identifier)):[10.1016/j.ejc.2011.12.005](https://doi.org/10.1016%2Fj.ejc.2011.12.005), [S2CID](/source/S2CID_(identifier)) [5530520](https://api.semanticscholar.org/CorpusID:5530520)

- [Fellows, Michael R.](/source/Michael_Fellows); [Rosamond, Frances A.](/source/Frances_A._Rosamond); Rotics, Udi; [Szeider, Stefan](/source/Stefan_Szeider) (2009), "Clique-width is NP-complete", *[SIAM Journal on Discrete Mathematics](/source/SIAM_Journal_on_Discrete_Mathematics)*, **23** (2): 909–939, [doi](/source/Doi_(identifier)):[10.1137/070687256](https://doi.org/10.1137%2F070687256), [MR](/source/MR_(identifier)) [2519936](https://mathscinet.ams.org/mathscinet-getitem?mr=2519936).

- Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket (2010), "Intractability of clique-width parameterizations", *[SIAM Journal on Computing](/source/SIAM_Journal_on_Computing)*, **39** (5): 1941–1956, [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.220.1712](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.220.1712), [doi](/source/Doi_(identifier)):[10.1137/080742270](https://doi.org/10.1137%2F080742270), [MR](/source/MR_(identifier)) [2592039](https://mathscinet.ams.org/mathscinet-getitem?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](/source/ArXiv_(identifier)):[2111.03492](https://arxiv.org/abs/2111.03492), [doi](/source/Doi_(identifier)):[10.1145/3519935.3519996](https://doi.org/10.1145%2F3519935.3519996), [S2CID](/source/S2CID_(identifier)) [243832882](https://api.semanticscholar.org/CorpusID:243832882).

- [Golumbic, Martin Charles](/source/Martin_Charles_Golumbic); Rotics, Udi (2000), "On the clique-width of some perfect graph classes", *International Journal of Foundations of Computer Science*, **11** (3): 423–443, [doi](/source/Doi_(identifier)):[10.1142/S0129054100000260](https://doi.org/10.1142%2FS0129054100000260), [MR](/source/MR_(identifier)) [1792124](https://mathscinet.ams.org/mathscinet-getitem?mr=1792124).

- Gurski, Frank; Wanke, Egon (2000), "The tree-width of clique-width bounded graphs without *Kn,n*", in [Brandes, Ulrik](/source/Ulrik_Brandes); [Wagner, Dorothea](/source/Dorothea_Wagner) (eds.), *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](/source/Doi_(identifier)):[10.1007/3-540-40064-8_19](https://doi.org/10.1007%2F3-540-40064-8_19), [MR](/source/MR_(identifier)) [1850348](https://mathscinet.ams.org/mathscinet-getitem?mr=1850348).

- Gurski, Frank; Wanke, Egon (2007), "Line graphs of bounded clique-width", *[Discrete Mathematics](/source/Discrete_Mathematics_(journal))*, **307** (22): 2734–2754, [doi](/source/Doi_(identifier)):[10.1016/j.disc.2007.01.020](https://doi.org/10.1016%2Fj.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](/source/Discrete_Applied_Mathematics)*, **157** (4): 583–595, [doi](/source/Doi_(identifier)):[10.1016/j.dam.2008.08.031](https://doi.org/10.1016%2Fj.dam.2008.08.031), [MR](/source/MR_(identifier)) [2499471](https://mathscinet.ams.org/mathscinet-getitem?mr=2499471).

- Hliněný, Petr; [Oum, Sang-il](/source/Oum_Sang-il) (2008), "Finding branch-decompositions and rank-decompositions", *[SIAM Journal on Computing](/source/SIAM_Journal_on_Computing)*, **38** (3): 1012–1032, [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.94.2272](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.2272), [doi](/source/Doi_(identifier)):[10.1137/070685920](https://doi.org/10.1137%2F070685920), [MR](/source/MR_(identifier)) [2421076](https://mathscinet.ams.org/mathscinet-getitem?mr=2421076).

- [Oum, Sang-il](/source/Oum_Sang-il); [Seymour, Paul](/source/Paul_Seymour_(mathematician)) (2006), "Approximating clique-width and branch-width", *[Journal of Combinatorial Theory](/source/Journal_of_Combinatorial_Theory)*, Series B, **96** (4): 514–528, [doi](/source/Doi_(identifier)):[10.1016/j.jctb.2005.10.006](https://doi.org/10.1016%2Fj.jctb.2005.10.006), [MR](/source/MR_(identifier)) [2232389](https://mathscinet.ams.org/mathscinet-getitem?mr=2232389).

- [Oum, Sang-il](/source/Oum_Sang-il) (2008), "Approximating rank-width and clique-width quickly", *[ACM Transactions on Algorithms](/source/ACM_Transactions_on_Algorithms)*, **5** (1): Art. 10, 20, [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.574.8156](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.574.8156), [doi](/source/Doi_(identifier)):[10.1145/1435375.1435385](https://doi.org/10.1145%2F1435375.1435385), [MR](/source/MR_(identifier)) [2479181](https://mathscinet.ams.org/mathscinet-getitem?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](/source/Doi_(identifier)):[10.1007/978-3-540-39890-5_32](https://doi.org/10.1007%2F978-3-540-39890-5_32), [MR](/source/MR_(identifier)) [2080095](https://mathscinet.ams.org/mathscinet-getitem?mr=2080095).

- Wanke, Egon (1994), "k-NLC graphs and polynomial algorithms", *[Discrete Applied Mathematics](/source/Discrete_Applied_Mathematics)*, **54** (2–3): 251–266, [doi](/source/Doi_(identifier)):[10.1016/0166-218X(94)90026-4](https://doi.org/10.1016%2F0166-218X%2894%2990026-4), [MR](/source/MR_(identifier)) [1300250](https://mathscinet.ams.org/mathscinet-getitem?mr=1300250).

---
Adapted from the Wikipedia article [Clique-width](https://en.wikipedia.org/wiki/Clique-width) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Clique-width?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.