Split graph

This article is about graphs that can be partitioned into a clique and an independent set. For cuts that form complete bipartite graphs, see split (graph theory).
A split graph, partitioned into a clique and an independent set.

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer (1977a, 1977b), and independently introduced by Tyshkevich and Chernyak (1979), where they called these graphs "polar graphs" (Russian: полярные графы).[1]

A split graph may have more than one partition into a clique and an independent set; for instance, the path a–b–c is a split graph, the vertices of which can be partitioned in three different ways:

  1. the clique {a, b} and the independent set {c}
  2. the clique {b, c} and the independent set {a}
  3. the clique {b} and the independent set {a, c}

Split graphs can be characterized in terms of their forbidden induced subgraphs: a graph is split if and only if no induced subgraph is a cycle on four or five vertices, or a pair of disjoint edges (the complement of a 4-cycle).[2]

  1. ^ Földes & Hammer (1977a) had a more general definition, in which the graphs they called split graphs also included bipartite graphs (that is, graphs that be partitioned into two independent sets) and the complements of bipartite graphs (that is, graphs that can be partitioned into two cliques). Földes & Hammer (1977b) use the definition given here, which has been followed in the subsequent literature; for instance, it is Brandstädt, Le & Spinrad (1999), Definition 3.2.3, p.41.
  2. ^ Földes & Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151.