Page 118 - Textos de Matemática Vol. 39

108 RUSSELL MERRIS
μ ≻ ν if and only if F(ν) can be obtained from F(μ) by moving boxes down, to higher numbered rows.
F(μ) =
B(μ) =

= R(μ)

Figure 1 Figure 2
Following [12; 14], denote by R(μ) that part of F(μ) consisting of the boxes on or to the right of the main diagonal (darkened in Fig.s 1-2), and by B(μ) what is left of F(μ) when R(μ) is removed. As illustrated in Fig. 2, B(μ) is comprised of the boxes of F(μ) strictly below the diagonal. Denote by ρ(μ) and β(μ) the (strict) partitions whose parts are the lengths of the rows of R(μ) and the columns of B(μ), respectively.
Theorem 1.1. Partition π ⊢ 2m is graphic if and only if β(π) weakly subma- jorizes ρ(π).
Frequently attributed to H¨asselbarth [7], (an equivalent form of) Theo- rem 1.1 was first published by Ruch and Gutman [17].
2. Minimal Split Graphs.
In the special case that β(π) majorizes ρ(π), π is called a split partition. A split graph is one whose degree sequence is a split partition. First introduced in [5], G = (V,E) is a split graph if and only if V can be partitioned into the disjoint union of a clique and an independent set (either of which may be empty), if and only if G does not have an induced subgraph isomorphic to one of the three forbidden graphs 2K2, C4, or C5, if and only if both G and its complement, Gc, are chordal.
Special even among split partitions are the threshold partitions, those for which β(π) = ρ(π). Maximal with respect to majorization among graphic partitions, threshold partitions are unigraphic, i.e., up to isomorphism, they are realized uniquely by the (aptly named) threshold graphs.
Denote by Par(2m) the set of (all) partitions of 2m, partially ordered by majorization. Illustrated in Fig. 3 is the ”Hasse diagram” for the subposet of Par(12) consisting of the split partitions. The four maximal split (threshold) partitions and the two minimal split partitions, (33, 13) and (4, 3, 15), are shown using dark boxes.