AROUND THE ERDÖS–GALLAI CRITERION

Abstract

By an (integer) partition we mean a non-increasing sequence λ = (λ1,λ2,…) of non-negative integers that contains a finite number of non-zero components. A partition λ is said to be graphic if there exists a graph G such that λ = dptG, where we denote by dptG the degree partition of G composed of the degrees of its vertices, taken in non-increasing order and added with zeros. In this paper, we propose to consider another criterion for a partition to be graphic, the ht-criterion, which, in essence, is a convenient and natural reformulation of the well-known Erdös-Gallai criterion for a sequence to be graphical. The ht-criterion fits well into the general study of lattices of integer partitions and is convenient for applications. The paper shows the equivalence of the Gale-Ryser criterion on the realizability of a pair of partitions by bipartite graphs, the ht-criterion and the Erdös-Gallai criterion. New proofs of the Gale-Ryser criterion and the Erdös-Gallai criterion are given. It is also proved that for any graphical partition there exists a realization that is obtained from some splitable graph in a natural way. A number of information of an overview nature is also given on the results previously obtained by the authors which are close in subject matter to those considered in this paper.