Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 

 

On a variation of the Ramsey number


Authors: Gary Chartrand and Seymour Schuster
Journal: Trans. Amer. Math. Soc. 173 (1972), 353-362
MSC: Primary 05C35
DOI: https://doi.org/10.1090/S0002-9947-1972-0317992-9
MathSciNet review: 0317992
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ c(m,n)$ be the least integer $ p$ such that, for any graph $ G$ of order $ p$, either $ G$ has an $ m$-cycle or its complement $ \bar G$ has an $ n$-cycle. Values of $ c(m,n)$ are established for $ m,n \leqslant 6$ and general formulas are proved for $ c(3,n),c(4,n)$, and $ c(5,n)$.


References [Enhancements On Off] (What's this?)

  • [1] Jack E. Graver and James Yackel, Some graph theoretic results associated with Ramsey’s theorem, J. Combinatorial Theory 4 (1968), 125–175. MR 0225685
  • [2] Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR 0256911
  • [3] F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1930), 264-286.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C35

Retrieve articles in all journals with MSC: 05C35


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1972-0317992-9
Keywords: Graph, cycle, Ramsey number, complement
Article copyright: © Copyright 1972 American Mathematical Society