Splittance
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. Calculation 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  be any graph with  vertices, whose degrees in decreasing order are . Let  be the largest index for which . Then the splittance of  is

The given graph is a split graph already if . Otherwise, it can be made into a split graph by calculating , adding all missing edges between pairs of the  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. Applications
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. References

Graph invariants