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).

[15][16] In particular, every graph property that can be expressed in MSO1 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.