Clique-width cw(G): minimum labels k to build G using 4 operations: ①create labeled vertex, ②disjoint union, ③relabel i→j, ④join all i-labeled to all j-labeled. Cographs: cw≤2. Distance-hereditary: cw≤3. tw+1 ≤ cw ≤ 2^(tw+1).
How to Use
Select graph:
- cw: Clique-width
- Labels: Construction
- vs tw: Compare
Four Operations
①Create: single vertex with label i. ②Union: combine two graphs. ③Relabel: change all label i to j. ④Join: add all edges between label i and label j. These four operations generate all graphs.
Courcelle's Theorem
Every MSO₁-definable property decidable in O(n) time on bounded clique-width graphs (given decomposition). Extends Courcelle's theorem for treewidth to dense graphs. Powerful meta-theorem.
Step-by-Step Instructions
- 1Select graph.
- 2Compute cw.
- 3Build expression.
- 4Count labels.
- 5Apply MSO₁.