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

Abstract

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