Recognising graphs of bounded clique-width
For a fixed bound k, can it be decided in polynomial time whether a graph has clique-width at most k?
Summary
Clique-width measures how simply a graph can be built from labelled vertices; it is related to treewidth but can be small for dense graphs. Computing it exactly is NP-hard in general and graphs of clique-width at most 3 can be recognised in polynomial time, but for larger fixed bounds the question is open.
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 18 Nov 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.