Computation of the Ramsey number R(B_3, K_5)

Show full item record

Title: Computation of the Ramsey number R(B_3, K_5)
Author: Babak, Andrey; Radziszowski, Stanislaw; Tse, Kung-Kuen
Abstract: In 1989, George R. T. Hendry presented a table of two-color graph Ramsey numbers R(G,H) for all pairs of graphs G and H having five vertices, with the exception of seven cases. Until now, only two of the these open cases were solved. This work eliminates another one by computing R(B_3,K_5) = 20, where B_3 = K_2 + K_3 is the book graph of order 5. In addition, we show that for these parameters there exists a unique up to isomorphism critical graph. The results are based on computer algorithms. Among the four remaining open cases in Hendry's table, the most notable is that of K_5 versus K_5, for which it is known that 43<_R(K_5,K_5)<_49.
Record URI: http://hdl.handle.net/1850/9696
Date: 2004

Files in this item

Files Size Format View
SRadziszowskiArticle2004.pdf 114.0Kb 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

Browse