Graphs and pigeonholes

Gargano, Michael L. (2001) Graphs and pigeonholes. In: Robert J. Bumcrot Festschrift, 11 May 2001, Hofstra University.

Full text available as:

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
26 Kb


Sometimes the pigeonhole principle (PHP) is used to prove a result in graph theory. The following is a famous, well-known example: (Ramsey's Theorem) If the edges of a K6 are colored with red and blue then there is a K3 subgraph which is either all red or all blue. There are many other elegant applications of the pigeonhole principle. Presented here are some novel graph theory interpretations of a few of these PHP results.

Item Type:Conference or Workshop Item (Paper)
Additional Information:This paper was given at the Robert J. Bumcrot Festschrift on May 11, 2001.
Uncontrolled Keywords:graph theory pigeonhole principle
Subjects:Q Science > Q Science (General)
Q Science > QA Mathematics
ID Code:32
Deposited By:Admin HofPrints
Deposited On:03 January 2006

Repository Staff Only: edit this item