Vol. 41, No. 2, 1972

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 311: 1
Vol. 310: 1  2
Vol. 309: 1  2
Vol. 308: 1  2
Vol. 307: 1  2
Vol. 306: 1  2
Vol. 305: 1  2
Vol. 304: 1  2
Online Archive
The Journal
Editorial Board
Submission Guidelines
Submission Form
Policies for Authors
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author Index
To Appear
Other MSP Journals
Generalized Ramsey theory for graphs. III. Small off-diagonal numbers

Václáv Chvátal and Frank Harary

Vol. 41 (1972), No. 2, 335–345

The classical Ramsey theory for graphs studies the Ramsey numbers r(m,n). This is the smallest p such that every 2-coloring of the lines of the complete graph Kp contains a green Km or a red Kn. In the preceding papers in this series, we developed the theory and calculation of the diagonal numbers r(F) for a graph F with no isolated points, as the smallest p for which every 2-coloring of Kp contains a monochromatic F. Here we introduce the off-diagonal numbers: 7(F1,F2) with F1F2 is the minimum p such that every 2-coloring of Kp contains a green F1 or a red F2. With the help of a general lower bound, the exact values of r(F1,F2) are determined for all graphs Fi with less than five points having no isolates.

Mathematical Subject Classification 2000
Primary: 05C99
Secondary: 05A17
Received: 23 February 1971
Published: 1 May 1972
Václáv Chvátal
Frank Harary