A Computational approach for the Ramsey numbers R(C_4, K_n)

Show full item record

Redirect: RIT Scholars content from RIT Digital Media Library has moved from http://ritdml.rit.edu/handle/1850/7999 to RIT Scholar Works http://scholarworks.rit.edu/article/659, please update your feeds & links!
Title: A Computational approach for the Ramsey numbers R(C_4, K_n)
Author: Radziszowski, Stanislaw; Tse, Kung-Kuen
Abstract: For graphs G and H, the Ramsey number R(G,H) is the least integer n such that every 2-coloring of the edges of K_n contains a subgraph isomorphic to G in the first color or a subgraph isomorphic to H in the second color. Graph G is a (C_4, K_n)-graph if G doesn't contain a cycle C_4 and G has no independent set of order n. Jayawardene and Rousseau showed that 21 <= R(C_4,K_7) <= 22. In this work we determine R(C_4, K_7) = 22 and R(C_4,K_8) = 26, and enumerate various families of (C_4, K_n)-graphs. In particular, we construct all (C_4, K_n)-graphs for n < 7, and all (C_4,K_7)-graphs on at least 19 vertices. Most of the results are based on computer algorithms.
Record URI: http://hdl.handle.net/1850/7999
Date: 2002

Files in this item

Files Size Format View
SRadziszowskiArticle2002.pdf 165.2Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML

Advanced Search