Ramsey bounds for graph products

Paul Erdős, Robert James McEliece and Herbert Taylor

Vol. 37 (1971), No. 1, 45–46

DOI: 10.2140/pjm.1971.37.45

Abstract

Here we show that Ramsey numbers M(k₁,⋯,k_n) give sharp upper bounds for the independence numbers of product graphs, in terms of the independence numbers of the factors.

Mathematical Subject Classification 2000

Primary: 05C99

Milestones

Received: 25 May 1970

Published: 1 April 1971