Generalized pigeonhole properties of graphs and oriented graphs
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.
- A Pigeonhole Property for Relational Structures
- scientific article; zbMATH DE number 3823785 (Why is no real title available?)
- scientific article; zbMATH DE number 3767656 (Why is no real title available?)
- scientific article; zbMATH DE number 44603 (Why is no real title available?)
- scientific article; zbMATH DE number 524137 (Why is no real title available?)
- Indivisibility and alpha-morphisms
- Inexhaustible homogeneous structures
- On an adjacency property of almost all graphs
- Ramsey-type properties of relational structures
- The random graph
- Theory of relations. Transl. from the French by P. Clote
- Tournaments and Orders with the Pigeonhole Property
This page was built for publication: Generalized pigeonhole properties of graphs and oriented graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1612756)
