Generalized Ramsey Theory for Graphs V. the Ramsey Number of a Digraph

Continuing this series of papers on generalized Ramsey theory for graphs, we define the Ramsey number r(D l , D 2 ) of two digraphs D 1 and D 2 as the minimum p such that every 2‐colouring of the arcs (directed lines) of DK P (the complete symmetric digraph of order p ) contains a monochromatic D 1 or D 2 . It is shown(Theorem 1) that this number exists if and only if D 1 or D 2 is acyclic. Then r(D) , the diagonal Ramsey number of a given acyclic digraph D , is defined as r(D, D) . Notation: D′ is the converse of D, GD is the underlying graph of D, DG is the symmetric digraph of G , and T p is the transitive tournament of order p . Let r(m, n) be the traditional Ramsey number of the two complete graphs K m and K n . Finally, let S n be the star with n arcs from one point u to n points v i . Assuming the Ramsey numbers under discussion exist, we prove the following results: THEOREM 2. r(D 1 , D 2 ) = r(D 1 ′ D 2 ′) . THEOREM 3. r(D 1 , D 2 ) ⩾ r(GD 1 , GD 2 ) . THEOREM 4. r(D 1 , D 2 ) ⩽ r(T P1 , T P2 ) if both D 1 and D 2 (with p 1 and p 2 points respectively) are acyclic . THEOREM 5. r(T m , T n ) = r(m, n) . THEOREM 6. r(m, ri) ⩽ r(T m , DK n ) ⩽ r(2 m−1 , n) . THEOREM 7. r(S m , S n ) = r(S m , S n ′) = m+n . Finally, we establish all Ramsey numbers r(D 1 , D 2 ) for digraphs without isolates and with less than four points, and all diagonal Ramsey numbers r(D) of acyclic digraphs without isolates with less than five points.