Papex

Open problem · Computer science · Open

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.

More in Computing