Split (graph theory)

A graph with two nontrivial strong splits (top) and its split decomposition (bottom). The three quotient graphs are a star (left), a prime graph (center), and a complete graph (right).
This article is about cuts that form complete bipartite graphs. For graphs that can be partitioned into a clique and an independent set, see split graph.

In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms.

Splits and split decompositions were first introduced by Cunningham (1982), who also studied variants of the same notions for directed graphs.[1]

  1. ^ Cunningham, William H. (1982), "Decomposition of directed graphs", SIAM Journal on Algebraic and Discrete Methods, 3 (2): 214–228, doi:10.1137/0603021, MR 0655562.