Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: All Ramsey numbers r(K3, G) for connected graphs of order 9. | All Ramsey numbers r K3 G for connected graphs of order 9 Stephan Brandt Fachbereich Mathematik Informatik WE 2 Freie Universităt Berlin Arnimallee 3 14195 Berlin Germany brandt@ Gunnar Brinkmann Fakultat fur Mathematik Universitaăt Bielefeld 33501 Bielefeld Germany gunnar@ Thomas Harmuth Forschungsschwerpunkt Mathematisierung Universitaăt Bielefeld 33501 Bielefeld Germany harmuth@ Submitted September 4 1997 Accepted January 3 1998 Abstract We determine the Ramsey numbers r K3 G for all 261080 connected graphs of order 9 and further Ramsey numbers of this type for some graphs of order up to 12. Almost all of them were determined by computer programs which are based on a program for generating maximal triangle-free graphs. 1 Introduction For two graphs G and H the Ramsey number r G H is the smallest integer r such that every 2-colouring of Kr using the colours red and blue say contains G as a red subgraph or H as a blue subgraph. Equivalently r is the smallest integer such that 1AMS Subject Classification 05C55 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 5 1998 R7 2 every graph F of order p r contains G as a subgraph or its complement F contains H as a subgraph. The classical Ramsey numbers those where both G and H are complete graphs are notoriously difficult to compute or even to estimate for large order graphs. Also there are only a few precise results known for inhnite sequences of graphs. Usually only those cases are known where extremal graph theory and Ramsey theory meet. Here we will deal with Ramsey numbers r K3 H for connected graphs H of small order. A few years ago these numbers were completely determined only for graphs H up to order 6 the last and major step being done by Faudree Rousseau and Schelp 8 . Only recently the numbers for all connected graphs of order 7 were computed by Jin Xia 10 in his thesis by using a computer. Unfortunately his results are unreliable since some of the
