The EdgeCount Criterion for Graphic Lists We give a new short proof of Korenu0027s characterization of graphic lists, extended to multigraphs with bounded multiplicity p, called  pgraphs . The EdgeCount Criterion (ECC) for an integer ntuple d and integer p is the statement that for all disjoint sets I and J of indices, sum_iin I  d_isum_jin J p(n1)d_jge pI,J.  An integer list d is the degree list of a pgraph if and only if it has even sum and satisfies ECC. Analogous statements hold for bipartite or directed graphs, and an old characterization of degree lists of signed graphs follows as a corollary  of the extension to multigraphs.

Ordered graphs and large bicliques in intersection graphs of curves. An ordered graph G_ 0 such that every ordered graph on n vertices that does not contain a monotone path of length k as an induced subgraph has a vertex of degree at least c_kn, or its complement has a biclique of size at least c_knlog n. A similar result holds for ordered graphs containing no induced ordered subgraph isomorphic to a fixed ordered matching.  As a consequence, we give a short combinatorial proof of the following theorem of Fox and Pach. There exists a constant cu003e0 such the intersection graph G of any collection of n xmonotone curves in the plane has a biclique of size at least cnlog n or its complement contains a biclique of size at least cn. (A curve is called xmonotone if every vertical line intersects it in at most one point.) We also prove that if G has at most left(frac14 epsilonright)nchoose 2 edges for some epsilonu003e0, then overlineG contains a linear sized biclique. We show that this statement does not remain true if we replace frac14 by any larger constants.