Vol. 41, No. 2, 1972

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 325: 1
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Vol. 321: 1  2
Vol. 320: 1  2
Vol. 319: 1  2
Vol. 318: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Contacts
 
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
Abstract

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
Milestones
Received: 23 February 1971
Published: 1 May 1972
Authors
Václáv Chvátal
Frank Harary