Clique-width¶

The minimum number of labels needed to construct a graph by vertex creation, disjoint union, complete joins between labels, and relabeling.

Version: v2 · 2026-09-19 · History
Domain-specific #: 3710
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Graph Theory → Mathematics

Core Idea¶

A k-expression builds a labeled graph using four operations; clique-width is the least k for which some expression yields the graph after labels are forgotten. Labels summarize interchangeable vertex roles while bulk joins create all cross-label edges, so a short label vocabulary captures recursive graph structure including many dense families. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

The Fewest-Colors Builder

Imagine building a dot-and-line drawing using colored stickers and only four moves: add one dot with a color, put two drawings side by side, connect every dot of one color to every dot of another color, or change all dots of one color into another color. Clique-width is the smallest number of colors you need to build the drawing this way.

Building With Few Labels

Clique-width measures how simply a graph can be built. You build it with labels, like colors, using only four moves: make a new dot with a label, put two built graphs next to each other, connect every dot with label A to every dot with label B, and change every label A into label B. At the end you erase the labels. The clique-width of the graph is the smallest number of different labels that can build it. Because one move can add lots of lines at once, even very crowded graphs can have small clique-width.

Minimal Labeled-Construction Width

A k-expression builds a vertex-labeled graph with at most k labels using four operations: create a single vertex with a label, take the disjoint union of two labeled graphs, add all edges between vertices of label i and vertices of label j, and rename label i to label j. The clique-width of a graph is the smallest k such that some k-expression produces it once labels are ignored. Labels group vertices that will play interchangeable roles in future edge additions, and the bulk join adds many edges in one step. So even dense graphs, such as complete graphs, can have small clique-width. The value is a minimum over all valid expressions, so one expression only gives an upper bound.

Clique-width is the minimum number of labels k for which some k-expression yields a given graph after labels are forgotten. A k-expression is a term built from four operations on labeled graphs: creation of a single vertex with label i; disjoint union; relabeling all label-i vertices to label j; and the join that adds every edge between label-i and label-j vertices. Labels summarize classes of vertices that are interchangeable for all subsequent operations, and joins create all cross-label edges in one step, so a small label vocabulary can encode recursive structure even in dense graph families. The definition has two parts that must both hold: the graph is produced exactly by these four operations, and the width is minimized over all valid expressions, so exhibiting one k-expression only gives an upper bound. Clique-width thus generalizes the idea of bounded structural complexity beyond sparse graphs, and it should not be confused with treewidth or with clique size.

Scope of Application¶

Clique-width belongs to graph theory and is useful where the analyst can specify the typed graph theory carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, then evaluate the graph is produced exactly by the four allowed labeled operations and the width is minimal over all valid expressions. The scope is broad within that domain but bounded by the need for the graph is produced exactly by the four allowed labeled operations and the width is minimal over all valid expressions. The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the graph is produced exactly by the four allowed labeled operations and the width is minimal over all valid expressions the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test. A bare label is insufficient because the name Clique-width can be used for a formal identity, an implementation, or a neighboring result unless carrier and convention are stated.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Clique-width. Clique-width compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed graph theory carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the graph is produced exactly by the four allowed labeled operations and the width is minimal over all valid expressions independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of graph theory because they reuse the typed graph theory carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, Labels summarize interchangeable vertex roles while bulk joins create all cross-label edges, so a short label vocabulary captures recursive graph structure including many dense families., and type the carrier, state every parameter and convention in the definition, test that the graph is produced exactly by the four allowed labeled operations and the width is minimal over all valid expressions, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Clique-width Domain-specific

Parents (1) — outgoing typed relations

Clique-width is a kind of Complexity Prime

What makes it its own entry: the domain-specific identity determined by the graph is produced exactly by the four allowed labeled operations and the width is minimal over all valid expressions.

Hierarchy path (1) — routes to 1 parentless root

Clique-width → is a kind of Complexity

Neighborhood in Abstraction Space¶

Clique-width sits in a crowded region of the domain-specific corpus (1^st percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Graph Theory Structures & Invariants (48 abstractions)

Nearest neighbors

Split graph — 0.95
Join (graph theory) — 0.94
Intersection number (graph theory) — 0.94
Independent set (graph theory) — 0.93
Signed graph — 0.93

Computed from structural-signature embeddings · 2026-10-25