Generalized pigeonhole properties of graphs and oriented graphs (Q1612756)

The pigeonhole property (\(\mathcal P\)) is defined as follows: a relational structure \(A\) has (\(\mathcal P\)) if for every partition of the vertex set of \(A\) into two nonempty parts, the substructure induced by some of the parts is isomorphic to \(A\). A natural generalization is the property \({\mathcal P}(n,k)\). A relational structure \(A\) satisfies the \({\mathcal P}(n,k)\) property if whenever the vertex set of \(A\) is partitioned into \(n\) nonempty parts, the substructure induced by the union of some \(k\) of the parts is isomorphic to \(A\). The paper provides the complete classification of countable graphs, tournaments and oriented graphs with the \({\mathcal P}(3,2)\) property. Some contrasts to the classification of graphs with the \({\mathcal P}(2,1)\) property are pointed out. The paper concludes with some open problems.