Vol. 41, No. 2, 1972

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 329: 1
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
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