The Relative Oriented Clique Number of TriangleFree Planar Graphs Is 10. A vertex subset R of an oriented graph (overrightarrowG) is a relative oriented clique if each pair of nonadjacent vertices of R is connected by a directed 2path. The relative oriented clique number (omega _ro(overrightarrowG)) of (overrightarrowG) is the maximum value of R where R is a relative oriented clique of (overrightarrowG). Given a family (mathcal F) of oriented graphs, the relative oriented clique number is (omega _ro(mathcal F)  max omega _ro(overrightarrowG)overrightarrowG in mathcal F). For the family (mathcal P_4) of oriented trianglefree planar graphs, it was conjectured that (omega _ro(mathcal P_4)10). In this article, we prove the conjecture.

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.