Graph Blow-Up

A graph blow-up of a graph with vertices , , ..., is a graph obtained by replacing each vertex by a nonempty independent vertex set and replacing each graph edge by all the edges of the complete bipartite graph with parts and , with no additional edges (Illingworth 2022). Thus all vertices in a given set have the same graph neighborhood outside that set. The natural map from the blow-up to sends every vertex of to , so is the fiber over .

If , the resulting graph is often denoted . Its graph order and edge count are

and

When all , the blow-up is called uniform and is denoted by some authors. This exact-equality case is also called a balanced blow-up (Hatami et al. 2014). It is the graph lexicographic product , where is the empty graph on vertices. When the graph order is fixed but is not necessarily divisible by , "balanced" is also used when the fiber sizes differ by at most one (Avigad and Goldreich 2011).

Blow-ups of complete graphs are precisely the complete multipartite graphs. In particular, balanced blow-ups of complete graphs are Turán graphs.

This graph operation is distinct from algebraic blow-up and finite-time blow-up, and from the blow-up lemma, which concerns embedding graphs into regular pairs that approximate pairs of vertex sets inducing complete bipartite graphs in a graph blow-up.

Some graph-coloring literature instead replaces each original graph vertex by a nonempty clique. This clique-blowup convention differs from the independent vertex set replacement in the definition above. For these clique blowups, Huang et al. (2026) proved that every blowup of the cycle graph is recolorable iff is 3, 4, 5, or 7, where recolorability is defined by graph recoloring.