Generalized Ramsey theory for graphs. II. Small diagonal numbers

Chvátal, Václav; Harary, Frank

doi:10.1090/S0002-9939-1972-0332559-X

Generalized Ramsey theory for graphs. II. Small diagonal numbers
HTML articles powered by AMS MathViewer

by Václav Chvátal and Frank Harary PDF

Proc. Amer. Math. Soc. 32 (1972), 389-394 Request permission

Abstract:

Consider a finite nonnull graph G with no loops or multiple edges and no isolated points. Its Ramsey number $r(G)$ is defined as the minimum number p such that every 2-coloring of the lines of the complete graph ${K_p}$ must contain a monochromatic G. This generalizes the classical diagonal Ramsey numbers $r(n,n) = r({K_n})$ . We obtain the exact value of the Ramsey number of every such graph with at most four points.

References

Generalized Ramsey theory for graphs

Diagonal numbers

Václav Chvátal and Frank Harary, Generalized Ramsey theory for graphs. III. Small off-diagonal numbers, Pacific J. Math. 41 (1972), 335–345. MR 314696, DOI 10.2140/pjm.1972.41.335
A. W. Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959), 778–783. MR 107610, DOI 10.2307/2310464
R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canadian J. Math. 7 (1955), 1–7. MR 67467, DOI 10.4153/CJM-1955-001-4
Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911, DOI 10.21236/AD0705364
Frank Harary, The two-triangle case of the aquaintance graph, Math. Mag. 45 (1972), 130–135. MR 295962, DOI 10.2307/2687868