The Tyshkevich decomposition of a finite undirected simple graph of positive vertex count is its canonical ordered factorization under a split-graph composition operation. Every factor except the last is a split graph with a specified partition into a clique and an independent vertex set.
To define the operation, let 
be a split graph with a fixed
partition 
,
where 
is a clique and 
is an independent vertex
set. Either part may be empty. For a graph 
with a disjoint vertex set,
form the graph disjoint union of 
and 
, then add every edge from 
to 
.
Thus 
has vertex set 
and edge set
 |
The specified partition is part of the data. For example, the vertex of a singleton graph used as a left factor is
adjacent to every vertex
of 
when it lies in 
and is an isolated vertex
when it lies in 
(Barrus et al. 2025, author version, p. 4).
This operation is associative, using the combined clique and independent
vertex set when composing two split factors. It is not generally commutative.
A graph is indecomposable for this operation when it cannot
be expressed as 
with both 
and 
of positive vertex count.
Every finite undirected simple graph 
of positive vertex count admits a factorization
 |
where all factors have positive vertex count and are indecomposable, the 
are split graphs with the
displayed fixed partitions, and 
is not required to be split. The case 
is allowed. This factorization is unique up to graph
isomorphism, with factor order and the indicated clique/independent vertex set partitions preserved
(Tyshkevich 2000; Barrus et al. 2025, author version, p. 4). The final
factor 
may itself be split and has no specified partition in this notation. Thus the uniqueness
assertion does not assign a unique split partition to a single-vertex
final factor.
A graph is unigraphic iff every factor in its Tyshkevich decomposition is unigraphic (Tyshkevich 2000; Barrus et al. 2025, author version, p. 5). These factors are not in general the connected components of the graph.
