Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Clique-width
open-in-new
<h2 id="special-classes-of-graphs">Special classes of graphs</h2> <p><a href="/facts/Cograph/c3lYz8fV">Cographs</a> are exactly the graphs with clique-width at most 2.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> Every <a href="/facts/Distance-hereditary_graph/T17SFUmL">distance-hereditary graph</a> has clique-width at most 3. However, the clique-width of unit interval graphs is unbounded (based on their grid structure).<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> Similarly, the clique-width of bipartite permutation graphs is unbounded (based on similar grid structure).<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> 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.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p><p>Other graphs with bounded clique-width include the <a href="/facts/Leaf_power/5U2e17ta">k-leaf powers</a> for bounded values of k; these are the <a href="/facts/Induced_subgraph/G3EUC0MQ">induced subgraphs</a> of the leaves of a tree T in the <a href="/facts/Graph_power/KWL35z4P">graph power</a> <i>T</i><i>k</i>. However, leaf powers with unbounded exponents do not have bounded clique-width.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p> <h2 id="bounds">Bounds</h2> <p>Courcelle & Olariu (2000) and Corneil & Rotics (2005) proved the following bounds on the clique-width of certain graphs: </p> <ul><li>If a graph has clique-width at most k, then so does every <a href="/facts/Induced_subgraph/G3EUC0MQ">induced subgraph</a> of the graph.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a></li> <li>The <a href="/facts/Complement_graph/IdHUPFr3">complement graph</a> of a graph of clique-width k has clique-width at most 2<i>k</i>.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a></li> <li>The graphs of <a href="/facts/Treewidth/uoITxzRJ">treewidth</a> w have clique-width at most 3 · 2<i>w</i> − 1. The exponential dependence in this bound is necessary: there exist graphs whose clique-width is exponentially larger than their treewidth.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> In the other direction, graphs of bounded clique-width can have unbounded treewidth; for instance, n-vertex <a href="/facts/Complete_graph/AYD6hUqI">complete graphs</a> have clique-width 2 but treewidth <i>n</i> − 1. However, graphs of clique-width k that <a href="/facts/Biclique-free_graph/Dyb7xHPK">have no complete bipartite graph <i>K</i><i>t</i>,<i>t</i> as a subgraph</a> have treewidth at most 3<i>k</i>(<i>t</i> − 1) − 1. Therefore, for every family of <a href="/facts/Sparse_graph/xFC7b7s9">sparse graphs</a>, having bounded treewidth is equivalent to having bounded clique-width.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li> <li>Another graph parameter, the <a href="/facts/Rank-width/Kddc9Lk9">rank-width</a>, is bounded in both directions by the clique-width: rank-width ≤ clique-width ≤ 2rank-width + 1.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a></li></ul> <p>Additionally, if a graph G has clique-width k, then the <a href="/facts/Graph_power/KWL35z4P">graph power</a> <i>G</i>c has clique-width at most 2<i>kc</i><i>k</i>.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> 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 <i>G</i>c has clique-width at most 2(<i>c</i> + 1)<i>w</i> + 1 − 2, only singly exponential in the treewidth.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> </p> <h2 id="computational-complexity">Computational complexity</h2> Unsolved problem in mathematics: Can graphs of bounded clique-width be recognized in polynomial time? <a href="/facts/List_of_unsolved_problems_in_mathematics/RroxGPpP">(more unsolved problems in mathematics)</a> <p>Many optimization problems that are <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a> for more general classes of graphs may be solved efficiently by <a href="/facts/Dynamic_programming/CLcabtmk">dynamic programming</a> on graphs of bounded clique-width, when a construction sequence for these graphs is known.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a><a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> In particular, every <a href="/facts/Graph_property/bjuIvgb1">graph property</a> that can be expressed in MSO1 <a href="/facts/Monadic_second-order_logic/m9g3W9VP">monadic second-order logic</a> (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 <a href="/facts/Courcelle%2527s_theorem/Yy83uBvh">Courcelle's theorem</a>.<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> </p><p>It is also possible to find optimal <a href="/facts/Graph_coloring/J6HoBfP0">graph colorings</a> or <a href="/facts/Hamiltonian_cycle/MHjY2xoY">Hamiltonian cycles</a> 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.<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> The graphs of bounded clique-width are <a href="/facts/%25CE%25A7-bounded/K3zC7fQg">χ-bounded</a>, meaning that their chromatic number is at most a function of the size of their largest clique.<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> </p><p>The graphs of clique-width three can be recognized, and a construction sequence found for them, in polynomial time using an algorithm based on <a href="/facts/Split_decomposition/nW3Cf24B">split decomposition</a>.<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> For graphs of unbounded clique-width, it is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a> to compute the clique-width exactly, and also NP-hard to obtain an approximation with sublinear additive error.<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a> 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,<a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a> in particular in quadratic time in the number of vertices.<a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a> It remains open whether the exact clique-width, or a tighter approximation to it, can be calculated in <a href="/facts/Parameterized_complexity/RoyaJGgJ">fixed-parameter tractable time</a>, 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.<a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a> </p> <h2 id="related-width-parameters">Related width parameters</h2> <p>The theory of graphs of bounded clique-width resembles that for graphs of bounded <a href="/facts/Treewidth/uoITxzRJ">treewidth</a>, but unlike treewidth allows for <a href="/facts/Dense_graph/xFC7b7s9">dense graphs</a>. If a family of graphs has bounded clique-width, then either it has bounded treewidth or every <a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graph</a> is a subgraph of a graph in the family.<a class="footnote-ref" id="fnref:25" href="#fn:25"><sup>25</sup></a> Treewidth and clique-width are also connected through the theory of <a href="/facts/Line_graph/RWNxSy5j">line graphs</a>: a family of graphs has bounded treewidth if and only if their line graphs have bounded clique-width.<a class="footnote-ref" id="fnref:26" href="#fn:26"><sup>26</sup></a> </p><p>The graphs of bounded clique-width also have bounded <a href="/facts/Twin-width/RP69kLhS">twin-width</a>.<a class="footnote-ref" id="fnref:27" href="#fn:27"><sup>27</sup></a> </p> <h2 id="notes">Notes</h2> <ul><li>Bonnet, Édouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width I: Tractable FO model checking", <i><a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a></i>, 69 (1): A3:1–A3:46, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/2004.14789">2004.14789</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F3486655">10.1145/3486655</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=4402362">4402362</a></li> <li><a href="/facts/Andreas_Brandst%25C3%25A4dt/mtUmgW23">Brandstädt, A.</a>; Dragan, F.F.; Le, H.-O.; Mosca, R. (2005), "New graph classes of bounded clique-width", <i>Theory of Computing Systems</i>, 38 (5): 623–645, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.5994">10.1.1.3.5994</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00224-004-1154-6">10.1007/s00224-004-1154-6</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:2309695">2309695</a>.</li> <li><a href="/facts/Andreas_Brandst%25C3%25A4dt/mtUmgW23">Brandstädt, A.</a>; Engelfriet, J.; Le, H.-O.; Lozin, V.V. (2006), "Clique-width for 4-vertex forbidden subgraphs", <i>Theory of Computing Systems</i>, 39 (4): 561–590, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00224-005-1199-1">10.1007/s00224-005-1199-1</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:20050455">20050455</a>.</li> <li>Brandstädt, Andreas; Hundt, Christian (2008), "Ptolemaic graphs and interval graphs are leaf powers", <i>LATIN 2008: Theoretical informatics</i>, Lecture Notes in Comput. Sci., vol. 4957, Springer, Berlin, pp. 479–491, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-540-78773-0_42">10.1007/978-3-540-78773-0_42</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2472761">2472761</a>.</li> <li><a href="/facts/Andreas_Brandst%25C3%25A4dt/mtUmgW23">Brandstädt, A.</a>; Lozin, V.V. (2003), "On the linear structure and clique-width of bipartite permutation graphs", <i><a href="/facts/Ars_Combinatoria_(journal)/g86yo1Wy">Ars Combinatoria</a></i>, 67: 273–281, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.2000">10.1.1.16.2000</a>.</li> <li><a href="/facts/Janka_Chleb%25C3%25ADkov%25C3%25A1/vQY60msu">Chlebíková, J.</a> (1992), "On the tree-width of a graph", <i>Acta Mathematica Universitatis Comenianae</i>, New Series, 61 (2): 225–236, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.3900">10.1.1.30.3900</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1205875">1205875</a>.</li> <li>Cogis, O.; Thierry, E. (2005), "Computing maximum stable sets for distance-hereditary graphs", <i>Discrete Optimization</i>, 2 (2): 185–188, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.disopt.2005.03.004">10.1016/j.disopt.2005.03.004</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2155518">2155518</a>.</li> <li><a href="/facts/Derek_Corneil/IlyG5ET3">Corneil, Derek G.</a>; Habib, Michel; Lanlignel, Jean-Marc; <a href="/facts/Bruce_Reed_(mathematician)/rwrfNHpG">Reed, Bruce</a>; Rotics, Udi (2012), "Polynomial-time recognition of clique-width ≤ 3 graphs", <i><a href="/facts/Discrete_Applied_Mathematics/0xgV889h">Discrete Applied Mathematics</a></i>, 160 (6): 834–865, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.dam.2011.03.020">10.1016/j.dam.2011.03.020</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2901093">2901093</a>.</li> <li><a href="/facts/Derek_Corneil/IlyG5ET3">Corneil, Derek G.</a>; Rotics, Udi (2005), "On the relationship between clique-width and treewidth", <i><a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a></i>, 34 (4): 825–847, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2FS0097539701385351">10.1137/S0097539701385351</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2148860">2148860</a>.</li> <li><a href="/facts/Bruno_Courcelle/9148mMnR">Courcelle, Bruno</a>; Engelfriet, Joost; Rozenberg, Grzegorz (1993), "Handle-rewriting hypergraph grammars", <i>Journal of Computer and System Sciences</i>, 46 (2): 218–270, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0022-0000%2893%2990004-G">10.1016/0022-0000(93)90004-G</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1217156">1217156</a>. Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), <a href="/facts/MR_(identifier)/uP137L11">MR</a><a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1431281">1431281</a>.</li> <li><a href="/facts/Bruno_Courcelle/9148mMnR">Courcelle, B.</a> (1993), "Monadic second-order logic and hypergraph orientation", <i>Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science (LICS '93)</i>, pp. 179–190, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FLICS.1993.287589">10.1109/LICS.1993.287589</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:39254668">39254668</a>.</li> <li><a href="/facts/Bruno_Courcelle/9148mMnR">Courcelle, B.</a>; <a href="/facts/Johann_Makowsky/vMrntxNC">Makowsky, J. A.</a>; Rotics, U. (2000), "Linear time solvable optimization problems on graphs on bounded clique width", <i>Theory of Computing Systems</i>, 33 (2): 125–150, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.414.1845">10.1.1.414.1845</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs002249910009">10.1007/s002249910009</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:15402031">15402031</a>.</li> <li><a href="/facts/Bruno_Courcelle/9148mMnR">Courcelle, B.</a>; Olariu, S. (2000), <a href="https://digitalcommons.odu.edu/computerscience_fac_pubs/122">"Upper bounds to the clique width of graphs"</a>, <i><a href="/facts/Discrete_Applied_Mathematics/0xgV889h">Discrete Applied Mathematics</a></i>, 101 (1–3): 77–144, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0166-218X%2899%2900184-5">10.1016/S0166-218X(99)00184-5</a>.</li> <li>Dvořák, Zdeněk; Král', Daniel (2012), "Classes of graphs with small rank decompositions are χ-bounded", <i>Electronic Journal of Combinatorics</i>, 33 (4): 679–683, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1107.2161">1107.2161</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.ejc.2011.12.005">10.1016/j.ejc.2011.12.005</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:5530520">5530520</a></li> <li><a href="/facts/Michael_Fellows/Mmlrxg5L">Fellows, Michael R.</a>; <a href="/facts/Frances_A._Rosamond/Dtr4MJvG">Rosamond, Frances A.</a>; Rotics, Udi; <a href="/facts/Stefan_Szeider/ddRnrIxf">Szeider, Stefan</a> (2009), "Clique-width is NP-complete", <i><a href="/facts/SIAM_Journal_on_Discrete_Mathematics/7BG23qL5">SIAM Journal on Discrete Mathematics</a></i>, 23 (2): 909–939, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F070687256">10.1137/070687256</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2519936">2519936</a>.</li> <li>Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket (2010), "Intractability of clique-width parameterizations", <i><a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a></i>, 39 (5): 1941–1956, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.220.1712">10.1.1.220.1712</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F080742270">10.1137/080742270</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2592039">2592039</a>.</li> <li>Fomin, Fedor V.; Korhonen, Tuukka (2022), "Fast FPT-approximation of branchwidth", <i>Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing</i>, ACM, pp. 886–899, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/2111.03492">2111.03492</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F3519935.3519996">10.1145/3519935.3519996</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:243832882">243832882</a>.</li> <li><a href="/facts/Martin_Charles_Golumbic/jjoIMseL">Golumbic, Martin Charles</a>; Rotics, Udi (2000), "On the clique-width of some perfect graph classes", <i>International Journal of Foundations of Computer Science</i>, 11 (3): 423–443, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1142%2FS0129054100000260">10.1142/S0129054100000260</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1792124">1792124</a>.</li> <li>Gurski, Frank; Wanke, Egon (2000), "The tree-width of clique-width bounded graphs without <i>Kn,n</i>", in <a href="/facts/Ulrik_Brandes/LUPCvR6c">Brandes, Ulrik</a>; <a href="/facts/Dorothea_Wagner/1ztwNs8L">Wagner, Dorothea</a> (eds.), <i>Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Germany, June 15–17, 2000, Proceedings</i>, Lecture Notes in Computer Science, vol. 1928, Berlin: Springer, pp. 196–205, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-40064-8_19">10.1007/3-540-40064-8_19</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1850348">1850348</a>.</li> <li>Gurski, Frank; Wanke, Egon (2007), "Line graphs of bounded clique-width", <i><a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a></i>, 307 (22): 2734–2754, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.disc.2007.01.020">10.1016/j.disc.2007.01.020</a>.</li> <li>Gurski, Frank; Wanke, Egon (2009), "The NLC-width and clique-width for powers of graphs of bounded tree-width", <i><a href="/facts/Discrete_Applied_Mathematics/0xgV889h">Discrete Applied Mathematics</a></i>, 157 (4): 583–595, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.dam.2008.08.031">10.1016/j.dam.2008.08.031</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2499471">2499471</a>.</li> <li>Hliněný, Petr; <a href="/facts/Oum_Sang-il/hTzPCJpv">Oum, Sang-il</a> (2008), "Finding branch-decompositions and rank-decompositions", <i><a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a></i>, 38 (3): 1012–1032, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.2272">10.1.1.94.2272</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F070685920">10.1137/070685920</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2421076">2421076</a>.</li> <li><a href="/facts/Oum_Sang-il/hTzPCJpv">Oum, Sang-il</a>; <a href="/facts/Paul_Seymour_(mathematician)/AJp2GgAC">Seymour, Paul</a> (2006), "Approximating clique-width and branch-width", <i><a href="/facts/Journal_of_Combinatorial_Theory/oYS6G76K">Journal of Combinatorial Theory</a></i>, Series B, 96 (4): 514–528, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.jctb.2005.10.006">10.1016/j.jctb.2005.10.006</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2232389">2232389</a>.</li> <li><a href="/facts/Oum_Sang-il/hTzPCJpv">Oum, Sang-il</a> (2008), "Approximating rank-width and clique-width quickly", <i><a href="/facts/ACM_Transactions_on_Algorithms/8gsUjj7j">ACM Transactions on Algorithms</a></i>, 5 (1): Art. 10, 20, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.574.8156">10.1.1.574.8156</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1435375.1435385">10.1145/1435375.1435385</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2479181">2479181</a>.</li> <li>Todinca, Ioan (2003), "Coloring powers of graphs of bounded clique-width", <i>Graph-theoretic concepts in computer science</i>, Lecture Notes in Comput. Sci., vol. 2880, Springer, Berlin, pp. 370–382, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-540-39890-5_32">10.1007/978-3-540-39890-5_32</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2080095">2080095</a>.</li> <li>Wanke, Egon (1994), "k-NLC graphs and polynomial algorithms", <i><a href="/facts/Discrete_Applied_Mathematics/0xgV889h">Discrete Applied Mathematics</a></i>, 54 (2–3): 251–266, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0166-218X%2894%2990026-4">10.1016/0166-218X(94)90026-4</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1300250">1300250</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Courcelle, Engelfriet & Rozenberg (1993). - 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 <a href="https://doi.org/10.1016%2F0022-0000%2893%2990004-G" target="_blank">https://doi.org/10.1016%2F0022-0000%2893%2990004-G</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Courcelle (1993). - 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 <a href="https://doi.org/10.1109%2FLICS.1993.287589" target="_blank">https://doi.org/10.1109%2FLICS.1993.287589</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Courcelle & Olariu (2000). - 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 <a href="https://digitalcommons.odu.edu/computerscience_fac_pubs/122" target="_blank">https://digitalcommons.odu.edu/computerscience_fac_pubs/122</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Golumbic & Rotics (2000). - 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 <a href="https://doi.org/10.1142%2FS0129054100000260" target="_blank">https://doi.org/10.1142%2FS0129054100000260</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Brandstädt & Lozin (2003). - 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 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.2000" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.2000</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Brandstädt et al. (2005); Brandstädt et al. (2006). - 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 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.5994" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.5994</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Brandstädt & Hundt (2008); Gurski & Wanke (2009). - 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 <a href="https://doi.org/10.1007%2F978-3-540-78773-0_42" target="_blank">https://doi.org/10.1007%2F978-3-540-78773-0_42</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Courcelle & Olariu (2000), Corollary 3.3. - 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 <a href="https://digitalcommons.odu.edu/computerscience_fac_pubs/122" target="_blank">https://digitalcommons.odu.edu/computerscience_fac_pubs/122</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Courcelle & Olariu (2000), Theorem 4.1. - 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 <a href="https://digitalcommons.odu.edu/computerscience_fac_pubs/122" target="_blank">https://digitalcommons.odu.edu/computerscience_fac_pubs/122</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Corneil & Rotics (2005), strengthening Courcelle & Olariu (2000), Theorem 5.5. - 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 <a href="https://doi.org/10.1137%2FS0097539701385351" target="_blank">https://doi.org/10.1137%2FS0097539701385351</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Gurski & Wanke (2000). - Gurski, Frank; Wanke, Egon (2000), "The tree-width of clique-width bounded graphs without Kn,n", in Brandes, Ulrik; Wagner, Dorothea (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:10.1007/3-540-40064-8_19, MR 1850348 <a href="https://doi.org/10.1007%2F3-540-40064-8_19" target="_blank">https://doi.org/10.1007%2F3-540-40064-8_19</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Oum & Seymour (2006). - 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 <a href="https://doi.org/10.1016%2Fj.jctb.2005.10.006" target="_blank">https://doi.org/10.1016%2Fj.jctb.2005.10.006</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Todinca (2003). - 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 <a href="https://doi.org/10.1007%2F978-3-540-39890-5_32" target="_blank">https://doi.org/10.1007%2F978-3-540-39890-5_32</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Gurski & Wanke (2009). - 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 <a href="https://doi.org/10.1016%2Fj.dam.2008.08.031" target="_blank">https://doi.org/10.1016%2Fj.dam.2008.08.031</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Cogis & Thierry (2005). - 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 <a href="https://doi.org/10.1016%2Fj.disopt.2005.03.004" target="_blank">https://doi.org/10.1016%2Fj.disopt.2005.03.004</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Courcelle, Makowsky & Rotics (2000). - 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 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.414.1845" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.414.1845</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Courcelle, Makowsky & Rotics (2000). - 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 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.414.1845" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.414.1845</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Fomin et al. (2010). - 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 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.220.1712" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.220.1712</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Dvořák & Král' (2012). - 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 <a href="https://arxiv.org/abs/1107.2161" target="_blank">https://arxiv.org/abs/1107.2161</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>Corneil et al. (2012). - 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 <a href="https://doi.org/10.1016%2Fj.dam.2011.03.020" target="_blank">https://doi.org/10.1016%2Fj.dam.2011.03.020</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Fellows et al. (2009). - 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 <a href="https://doi.org/10.1137%2F070687256" target="_blank">https://doi.org/10.1137%2F070687256</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>Oum & Seymour (2006); Hliněný & Oum (2008); Oum (2008); Fomin & Korhonen (2022). - 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 <a href="https://doi.org/10.1016%2Fj.jctb.2005.10.006" target="_blank">https://doi.org/10.1016%2Fj.jctb.2005.10.006</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Fomin & Korhonen (2022). - 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 <a href="https://arxiv.org/abs/2111.03492" target="_blank">https://arxiv.org/abs/2111.03492</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>Fellows et al. (2009). - 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 <a href="https://doi.org/10.1137%2F070687256" target="_blank">https://doi.org/10.1137%2F070687256</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> <li id="fn:25"><p>Gurski & Wanke (2000). - Gurski, Frank; Wanke, Egon (2000), "The tree-width of clique-width bounded graphs without Kn,n", in Brandes, Ulrik; Wagner, Dorothea (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:10.1007/3-540-40064-8_19, MR 1850348 <a href="https://doi.org/10.1007%2F3-540-40064-8_19" target="_blank">https://doi.org/10.1007%2F3-540-40064-8_19</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></p></li> <li id="fn:26"><p>Gurski & Wanke (2007). - 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 <a href="https://doi.org/10.1016%2Fj.disc.2007.01.020" target="_blank">https://doi.org/10.1016%2Fj.disc.2007.01.020</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></p></li> <li id="fn:27"><p>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 <a href="https://arxiv.org/abs/2004.14789" target="_blank">https://arxiv.org/abs/2004.14789</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></p></li> </ol>