Encyclopedia

Splittance

Distance of a graph from a split graph

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated February 8, 2026

In graph theory, a branch of mathematics, the splittance of an undirected graph measures its distance from a split graph. A split graph is a graph whose vertices can be partitioned into an independent set (with no edges within this subset) and a clique (having all possible edges within this subset). The splittance is the smallest number of edge additions and removals that transform the given graph into a split graph.

01Calculation from degree sequence

The splittance of a graph can be calculated only from the degree sequence of the graph, without examining the detailed structure of the graph. Let G be any graph with n vertices, whose degrees in decreasing order are d₁ ≥ d₂ ≥ d₃ ≥ … ≥ d_n. Let m be the largest index for which d_i ≥ i, 1. Then the splittance of G is

$\sigma (G)={\tbinom {m}{2}}-{\frac {1}{2}}\sum _{i=1}^{m}d_{i}+{\frac {1}{2}}\sum _{i=m+1}^{n}d_{i}.$

The given graph is a split graph already if σ(G) = 0. Otherwise, it can be made into a split graph by calculating m, adding all missing edges between pairs of the m vertices of maximum degree, and removing all edges between pairs of the remaining vertices. As a consequence, the splittance and a sequence of edge additions and removals that realize it can be computed in linear time.

02Applications

The splittance of a graph has been used in parameterized complexity as a parameter to describe the efficiency of algorithms. For instance, graph coloring is fixed-parameter tractable under this parameter: it is possible to optimally color the graphs of bounded splittance in linear time.

Watch videos about SplittanceExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Splittance”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Splittance.svg by BagLuke, CC0

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.