A note on potentially Ks,t-bigraphic pairs

Abstract

Let A and B be nonincreasing lists of nonnegative integers, having lengths m and n, respectively. The pair (A; B) is bigraphic if there is a simple bipartite graph such that the lists of vertex degrees in the two partite sets are A and B. The pair (A; B) is potentially K_s,t-bigraphic if there is a simple bipartite graph containing K_s,t (with s vertices in the part of size m and t in the part of size n) such that the lists of vertex degrees in the two partite sets are A and B. We give a simplification of the Gale-Ryser characterization of bigraphic pairs and a simplification of the Gale-Ryser type characterization of potentially K_s,t-bigraphic pairs. Moreover, we give a simple sufficient condition of potentially K_s,tbigraphic pairs.