Vol. 41, No. 2, 1972

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 332: 1  2
Vol. 331: 1  2
Vol. 330: 1  2
Vol. 329: 1  2
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Online Archive
Volume:
Issue:
     
The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
Officers
 
Subscriptions
 
ISSN 1945-5844 (electronic)
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