Computation of the Ramsey number R(B_3, K_5)

Show simple item record Babak, Andrey Radziszowski, Stanislaw Tse, Kung-Kuen 2009-05-29T15:08:35Z 2009-05-29T15:08:35Z 2004
dc.identifier.citation Bulletin of the Institute of Combinatorics and Its Applications, 41 (2004) 71-76
dc.description.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.
dc.language.iso en_US
dc.publisher Institute of Combinatorics and Its Applications
dc.relation RIT Scholars content from RIT Digital Media Library has moved from to RIT Scholar Works, please update your feeds & links!
dc.relation.ispartofseries vol. 41
dc.subject Graph algorithmns en_US
dc.subject Ramsey numbers en_US
dc.title Computation of the Ramsey number R(B_3, K_5)
dc.type Article

Files in this item

Files Size Format View
SRadziszowskiArticle2004.pdf 114.0Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search RIT DML

Advanced Search