Generalized pigeonhole properties of graphs and oriented graphs

Anthony Bonato*, Peter J. Cameron, Dejan Delić, Stéphan Thomassé

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

A relational structure A satisfies the 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 P(2, 1) property is just the pigeonhole property, (P), introduced by Cameron, and studied by Bonato, Delić and Cameron. We classify the countable graphs, tournaments, and oriented graphs with the P(3, 2) property.

Original languageEnglish
Pages (from-to)257-274
Number of pages18
JournalEuropean Journal of Combinatorics
Volume23
Issue number3
DOIs
Publication statusPublished - 1 Jan 2002

Fingerprint

Dive into the research topics of 'Generalized pigeonhole properties of graphs and oriented graphs'. Together they form a unique fingerprint.

Cite this