All Ramsey numbers r(K_{3}, G) for connected graphs of order 9

Stephan Brandt Fachbereich Mathematik & Informatik, WE 2 Freie Universität Berlin Arnimallee 3 14195 Berlin, Germany

                    brandt@math.fu-berlin.de

Gunnar Brinkmann Fakultät für Mathematik Universität Bielefeld 33501 Bielefeld, Germany

                gunnar@mathematik.uni-bielefeld.de

Thomas Harmuth Forschungsschwerpunkt Mathematisierung Universität Bielefeld 33501 Bielefeld, Germany

               harmuth@mathematik.uni-bielefeld.de

Submitted: September 4, 1997; Accepted: January 3, 1998

Abstract

We determine the Ramsey numbers r(K_{3}, 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 K_{r}, 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 every graph F of order p ≥ r contains G as a subgraph, or its complement \overline{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 infinite 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(K_{3}, 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 numbers turned out to be incorrect. The correct numbers for all connected graphs of order 7 and 8 were computed by Brinkmann [3], also using a computer. Independently, Schelten and Schiermeyer computed the Ramsey numbers for graphs of order 7 by hand [15,16]. We will give the Ramsey numbers for all connected graphs of order 9. The Ramsey numbers up to r = 27 are determined by computer programs. The remaining numbers are computed by Ramsey theoretical means or were previously known. The computation of the Ramsey numbers for all graphs of order 10 seems currently out of reach, since the upper and lower bounds for the Ramsey numbers r(K_{3}, K_{10}) and r(K_{3}, K_{10} − e), respectively, both differ by 3 (see [14]). A second problem which we investigated is the concept of goodness introduced by Burr in [4]. A connected graph H is called G-good, if the Ramsey number r(G, H) is as small as possible for a connected graph H, or, in other words,

1AMS Subject Classification 05C55

r(G, H) = (χ(G) − 1)(|H| − 1) + s(G),  (1)

where χ(G) denotes the chromatic number and s(G) the chromatic surplus of G, i.e. the minimum cardinality of a color class taken over all proper χ(G) colorings of G. In the case G = K_{p} the most sparse connected graphs, namely trees, are known to be K_{p}-good [7]. In [5] the question was raised for the functions f(K_{p}, n) and g(K_{p}, n), where f(K_{p}, n) is the largest integer such that every connected graph of order n with at most f(K_{p}, n) edges is K_{p}-good and g(K_{p}, n) is the largest integer such that there is a K_{p}-good connected graph of order n with g(K_{p}, n) edges. We computed f(K_{3}, n) and g(K_{3}, n) for n ≤ 12. Because of the large number of small Ramsey numbers computed here, trends for the asymptotic growth of Ramsey numbers can be detected empirically. Some of them are opposed to the previously expected behaviour. Motivated by our data, in [1] the first author succeeded in disproving several goodness conjectures for more general classes of Ramsey numbers by purely theoretical (probabilistic) means. It should be mentioned that the observed behaviour can hardly be detected from the data on r(K_{3}, H) for graphs H of order at most 7, i.e. the range which can be solved without computer aid. We hope that our data will serve to give further insight into the growth of Ramsey numbers.

2 Computing r(K_{3}, H) for graphs of order 9

We computed the Ramsey numbers r(K_{3}, H) for connected graphs H of order 9 (presented in the listings at the end of this paper) mostly by using computer programs. The only exceptions are the cases r(K_{3}, K_{9}) = 36 and r(K_{3}, K_{9} − e) = 31 (which are well-known – see the regularly updated dynamic survey of Radziszowski [14]), r(K_{3}, K_{9} − K_{1,s}) = 28 for 2 ≤ s ≤ 7 and r(K_{3}, K_{9} − K_{3}) = 28 which are determined with the help of standard theoretical Ramsey arguments. The Ramsey number r(K_{3}, K_{n} − K_{1,s}) equals r(K_{3}, K_{n−1}) if s is sufficiently large with respect to n and r(K_{3}, K_{n−1}), as we will show now. Call a graph F a Ramsey graph for a pair of graphs (G, H), if F does not contain G as a subgraph and its complement \overline{F} does not contain H as a subgraph. In order to show that r(G, H) = r, two tasks have to be performed: (i) find a Ramsey graph of order r − 1 for (G, H), and (ii) show that no Ramsey graph of order r exists for (G, H). For (i) we can alternatively find a subgraph H′ ⊆ H with r(G, H′) = r.

Theorem 1 If r = r(K_{3}, K_{n−1}) and n ≥ s + 1 > (n − 2)(n − 1)/(r − n) then r(K_{3}, K_{n} − K_{1,s}) = r.

Proof. Since K_{n−1} ⊆ K_{n} − K_{1,s} we have r(K_{3}, K_{n} − K_{1,s}) ≥ r. Now take a trianglefree graph F of order r. We have to show that K_{n} − K_{1,s} is contained in the complement \overline{F}. If the maximum degree Δ(F) ≥ n then \overline{F} contains K_{n} since F is triangle-free and therefore K_{n} − K_{1,s}. So assume Δ(F) ≤ n − 1. By the definition of the Ramsey number, F must have an independent set S of n − 1 vertices. If Δ(F) = n − 1 choose S to be the neighbourhood of an (n − 1)-valent vertex v, otherwise choose v arbitrarily in V (F) \ S. In any case, each vertex in S has at most n − 2 neighbours in V (F) \ (S ∪ {v}), so one vertex w of the r − n vertices in V (F) \ (S ∪ {v}) has at most ⌊(n − 2)(n − 1)/(r − n)⌋ ≤ s neighbours in S. Hence K_{n} − K_{1,s} is contained in the subgraph of \overline{F} induced by S ∪ \{w\}. □

Recently, Kim proved that r(K_{3}, K_{n}) = Θ(n^{2}/ log n) [11], so Theorem 1 yields r(K_{3}, K_{n} − K_{1,s}) = r(K_{3}, K_{n−1}) if s = Ω(log n). In the case that we are mainly interested in (n = 9), Theorem 1 gives equality for s ≥ 2.

Corollary 1 r(K_{3}, K_{9} − K_{1,s}) = 28 for 2 ≤ s ≤ 8. □

Since the complement of a triangle-free graph contains K_{n} − K_{3} if and only if it contains K_{n} − K_{1,2}, Corollary 1 implies the following result.

Corollary 2 r(K_{3}, K_{9} − K_{3}) = 28. □

The algorithm

The central tool for the computation of the remaining 261071 Ramsey numbers r(K_{3}, H) for connected graphs H of order 9 and the further Ramsey numbers which we computed, is the computer program mtf described in [2]. This program is designed to generate all non-isomorphic maximal triangle-free graphs, but it is prepared to include certain restrictions into the generation process. One of these restrictions is to generate only Ramsey graphs for (K_{3}, H). The program mtf generates maximal triangle-free graphs F on n vertices from maximal triangle-free graphs F′ on n − 1 vertices in such a way that \overline{F′} ⊆ \overline{F} always holds. So if a graph H is contained in the complement of a maximal triangle-free graph F_{0}, it will be contained in the complement of all its descendants as well and therefore they cannot be a Ramsey graph for (K_{3}, H). The Ramsey number r(K_{3}, H) is one more than the maximum order of a Ramsey graph for (K_{3}, H). Note that a maximal triangle-free supergraph of a Ramsey graph for (K_{3}, H) of the same order is a Ramsey graph for (K_{3}, H) as well. More details can be found in [3] and [2]. The amount of time needed to compute a single Ramsey number r(K_{3}, H) turns out to depend mainly on the magnitude of r(K_{3}, H). Even though this Ramsey number is relatively small for most of the graphs considered here, the huge number of graphs under investigation makes it impossible to compute all the Ramsey numbers separately. The most time-consuming part is the subgraph testing routine, so, in order to improve the performance, we tried to reduce the number of subgraph tests. One method to do so is to test a group of graphs H_{0}, H_{1}, …, H_{t} simultaneously. These graphs are ordered with respect to subgraph relations, so whenever a graph H_{i} is found to be contained in the complement of a maximal triangle-free graph F, all the graphs that are subgraphs of H_{i} need not be tested, and – the other way round – whenever a graph H_{j} is found to be not contained in the complement of a maximal triangle-free graph F, all the graphs that are supergraphs of H_{j} need not be tested any more. Some tests showed that usually it is most efficient to start testing the minimal elements of the subgraph chains and then proceed to the larger ones. This method was used e.g. for the graphs K_{9} − iK_{2} for 2 ≤ i ≤ 4. For very large groups this method is not optimal. The graphs have to be kept in the main memory of the computer for quick access, which requires machines with a lot of memory. Furthermore a lot of useless work is done if the subgraph chains are traversed in a direction where no information is gained. So for larger lists we optimized the methods already used in [3], developing a strategy which has the following property: to generate the Ramsey numbers for all connected graphs of order n with Ramsey number at most r_{0}, only the Ramsey numbers of the maximal elements of the subgraph lattice with Ramsey number r ≤ r_{0} are actually computed and the time needed for the whole computation is dominated by the time needed to compute these Ramsey numbers. As n grows, the number of maximal elements becomes negligible compared to the number of graphs altogether. Our approach is as follows: Assume that we already know the graphs of order n with Ramsey number smaller than r. Testing graphs for Ramsey number r we give a (possibly empty) list of MINGRAPHs, that are graphs of order at most n which are known to have Ramsey number larger than r. Furthermore we have a list of MAXGRAPHs, that are the maximal elements (w.r.t. inclusion) of the subgraph lattice with Ramsey number r, which is empty in the beginning, and, finally, a list of RAMSEYGRAPHs, containing triangle-free graphs of order r which are (or might be) Ramsey graphs for (K_{3}, H) for some graph H of order n. This list can be empty in the beginning, but may also contain graphs which we consider to be candidates for being Ramsey graphs. Then the basic structure of the algorithm can be explained as follows:

for k = \binom{n}{2} downto n − 1 do

for every connected graph H with k edges in the list do if H is not contained in any MAXGRAPH then

if H is not supergraph of one of the MINGRAPHs then

if H is contained in the complement of every RAMSEYGRAPH then

if mtf applied to H finds a Ramsey graph of order r then

add this Ramsey graph to the list of RAMSEYGRAPHs; r(K_{3}, H) > r else add H to the list of MAXGRAPHs; r(K_{3}, H) ≤ r

else r(K_{3}, H) > r

else r(K_{3}, H) > r
else r(K_{3}, H) ≤ r.

MAXGRAPHs and RAMSEYGRAPHs are always ordered according to the number of times they could be used to determine the Ramsey number of a graph, so that the graphs are first tested against the most promising MAXGRAPHSs and RAMSEY-GRAPHs. Graphs with the same number of edges can be tested in parallel. We ran this program on a large cluster of workstations in Berlin and Bielefeld using the program autoson [13] to distribute the jobs. Only some small amount of communication between the processes was necessary in order to distribute new RAMSEYGRAPHs and MAXGRAPHs. This was done by using a common file system. The main problem was that each level k had to be worked out completely before the computations for smaller sized graphs could start. Some tests starting runs on smaller size graphs before the larger size computations were completed lead to an enormous amount of computational overlap, so we did not follow this strategy any further. The graphs of order n to be tested were generated by the program makeg [12]. In our computations the average time needed to compute a MAXGRAPH is significantly longer than the average time needed to compute a RAMSEYGRAPH, while the time needed to test a graph against all existing MIN-, MAX-, and RAMSEY-GRAPHs is negligible. Since typically more MAXGRAPHs are generated than RAM-SEYGRAPHs, the time needed for the whole computation is dominated by the time needed to determine the MAXGRAPHs. So significant improvements in the running time, which are necessary for extending the results, requires improvements in the computation process of a single Ramsey number r(K_{3}, H). To compute r(K_{3}, H) for the graphs of order 9 and 10, we used the method described above, some preliminary methods on the way from those described in [3], and some runs testing small groups. Our data suggest the following conjecture:

Conjecture 1 For every integer r > 10 there is a connected graph H with r(K_{3}, H) = r.

There are no such graphs for r = 1, 2, 4, 8, 10 but we believe that for every other order such a graph exists.

3 The functions f(K_{3}, n) and g(K_{3}, n)

As already mentioned in the introduction, the function f(K_{p}, n) is the largest integer, such that every connected graph H of order n and size at most f(K_{p}, n) satisfies r(K_{p}, H) = (p − 1)(n − 1) + 1, and the function g(K_{p}, n) is the largest integer, such that there exists a graph H of order n with g(K_{p}, n) edges satisfying r(K_{p}, H) = (p − 1)(n − 1) + 1. Since trees attain the indicated bound, f(K_{p}, n) and g(K_{p}, n) are well defined. Not much is known about g(K_{p}, n). Burr et.al. [5] proved that

Ω(n^{p/(p−1)}) ≤ g(K_{p}, n) ≤ O(n^{(p+2)/p}(log n)^{1−( \frac{2}{(p^{2}−p)} )})

and improved the lower bound by a factor of \sqrt{log n} for p = 3. There is a substantial gap between the upper and the lower bound, and even a reasonable conjecture for the structure of the graphs determining g(K_{p}, n) seems to be missing. Based on the graphs giving the lower bound for p = 3, a possible structure for the graphs determining g(K_{3}, n) was proposed by Faudree, Rousseau and Schelp [9, Question 2.32]. This structure consists of the disjoint union of complete graphs and an additional vertex joined to all other vertices. The values and graphs for n ≤ 12 which we computed are still too small to judge, but we would rather expect graphs of larger connectivity to determine g(K_{3}, n). The situation is different for f(K_{p}, n). For p ≥ 4 it was shown by Burr et.al. [5], that f(K_{p}, n) = n + o(n), while for p = 3 they proved that f(K_{3}, n) > 17n/15 for n ≥ 4. The general belief—expressed in a number of conjectures—was that the growth of f(K_{3}, n) is superlinear in n. Motivated by the present results, Brandt [1] proved that for every constant c, almost all (with probability tending to 1) regular graphs H of sufficiently large degree d have Ramsey number r(G, H) > c|H| for every non-bipartite graph G. This implies that f(K_{3}, n) is linear in n, and in fact it can be shown that f(K_{3}, n) < 12n for large n. This complements a result of Burr et. al. [6], saying that for every bipartite graph G and constant Δ, every graph H of sufficiently large order n with bounded maximum degree Δ(H) ≤ Δ is G-good, i.e. r(G, H) = n − 1 + s(G). It is very likely that the bound f(K_{3}, n) < 12n is fairly weak. For small values of n for which we computed the exact numbers we have f(K_{3}, n) < 5n/2, but it seems likely that the exact values for larger n are somewhat larger. Though it seems difficult to guess a precise bound for f(K_{3}, n)/n as n → ∞, it may be simpler to guess the right Ramsey graphs, i.e. the triangle-free graphs F of order 2n − 1 for which there is a connected graph H of order n and size f(K_{3}, n) + 1 which is not contained in the complement of F. Possibly the typical Ramsey graphs are obtained from the lexicographic products C_{5}[\overline{K}_{k}] (obtained from a 5-cycle by replacing every vertex by a set of k independent vertices and joining any two sets if the corresponding vertices were adjacent in the 5-cycle) by deleting some vertices to adjust the order. This is the case for many small n and for large n these graphs suffice to show that f(K_{3}, n) has linear growth in n. So we pose the following problem:

Problem 1 Is it true that for every sufficiently large integer n there is a graph obtained from C_{5}[\overline{K}_{k}], k = ⌈(2n − 1)/5⌉, by deleting 5⌈(2n − 1)/5⌉ − 2n + 1 vertices, which is a Ramsey graph for (K_{3}, H), where H is a connected graph of order n and size f(K_{3}, n) + 1?

The strong impact of these graphs would also explain the strange behaviour of f(K_{3}, n). Note that f(K_{3}, 11) = f(K_{3}, 12) = 23, which was a surprising fact for us. In fact, we do not even know whether f(K_{3}, n) is a monotonously increasing function in n. If the answer to Problem 1 was affirmative, this would probably turn the determination of f(K_{3}, n) into a separator type problem, essentially asking for the smallest size of a graph of order n without a (\frac{1}{3}–\frac{2}{3})-separator of cardinality at most 2n/5. A (\frac{1}{3}–\frac{2}{3})-separator is a vertex set X ⊆ V (G) such that V (G) − X can be partitioned into two disjoint sets A, B with |A| ≤ |B| ≤ 2|A| with no edge joining a vertex of A to a vertex of B. Extending the above question even further, for f(K_{p}, n), p ≥ 4, the upper bound on f(K_{p}, n) suggests that the classical Ramsey graphs (i.e those for (K_{p}, K_{r})) might be among the relevant Ramsey graphs, which have a complex structure in contrast to the (possibly) simply structured Ramsey graphs for p = 3. Now, if G is non-bipartite with clique number p = 2, what are the relevant Ramsey graphs determining f(G, n)? The smallest example to look at is G = C_{5}.

Computing explicit values for f(K_{3}, n) and g(K_{3}, n)

We computed all values of f(K_{3}, n) and g(K_{3}, n) for n ≤ 12. The results are presented in Table 1. For n ≤ 10 we determined all K_{3}-good graphs, i.e. those with Ramsey number 2n − 1 by the above methods, so the values of f(K_{3}, n) and g(K_{3}, n) could be directly read off the lists. This showed some unexpected properties of the K_{3}-good graphs: The maximal elements of the subgraph chains are all much larger than the smallest graphs with larger Ramsey number. So we defined h(K_{3}, n) to be the smallest number h so that there is a graph G with n vertices and Ramsey number 2n−1 that is not contained in a larger graph with this property. Obviously f(K_{3}, n) ≤ h(K_{3}, n) ≤ g(K_{3}, n), but in all the observed cases h(K_{3}, n) is much closer to g(K_{3}, n) than to f(K_{3}, n).

Problem 2 What is the relation between f(K_{3}, n), h(K_{3}, n) and g(K_{3}, n)? Is it true in general that h(K_{3}, n)/f(K_{3}, n) ≥ g(K_{3}, n)/h(K_{3}, n) ?

Because of the enormous amount of graphs and the quickly increasing time for computing a single Ramsey number, for n ≥ 11 we could not determine all graphs with Ramsey number 2n − 1. For n = 10 there were already 334 maximal elements of the subgraph chains, 23 of them with g(K_{3}, 10) edges. For n = 11 we computed 151 maximal elements with g(K_{3}, 11) edges before we stopped the computations and looked for a faster way. Another astonishing property of the class of K_{3}-good graphs made it possible to determine even f(K_{3}, 12): It turned out that in general only very few graphs with g(K_{3}, n) edges are needed to decide that all graphs with f(K_{3}, n) edges have Ramsey number 2n − 1. To be precise: All graphs on 10 vertices with f(K_{3}, 10) edges are contained in the first two graphs on 10 vertices with g(K_{3}, 10) edges which we computed. For n = 11 the first 19 graphs were needed, but taking just graph number 1 and graph number 19 again gave a list of only two graphs that contained every graph on 11 vertices with f(K_{3}, 11) edges. In general, when testing a graph, mtf was much faster in finding Ramsey graphs than determining that no Ramsey graph of the given order exists for the testgraph. So our strategy was as follows: We guessed an upper bound b_{g} for g(K_{3}, n) and tested all graphs with b_{g} edges for being K_{3}-good. The result was either a number of Ramsey graphs or a set of graphs which are K_{3}-good or both. In case of K_{3}-good graphs we increased b_{g} and tested again, in case of no K_{3}-good graphs we decreased b_{g} and tested the smaller graphs. As soon as some K_{3}-good graph with e edges is found and all graphs with e+1 edges are shown not to be K_{3}-good, we know g(K_{3}, n) = e. Then the set of maximal K_{3}-good graphs known so far is taken and tested against a guess b_{f} for a lower bound of f(K_{3}, n). In case that all graphs with n vertices and b_{f} edges are contained in some of the maximal K_{3}-good graphs, we increase b_{f}, otherwise we either have to generate more of the K_{3}-good graphs of large size or to test the graphs separately whose Ramsey number could not be determined in this way. For n = 12 two K_{3}-good graphs with g(K_{3}, 12) edges and two with g(K_{3}, 12) − 1 edges were sufficient to contain all graphs on 12 vertices with 23 edges. For 24 edges one graph was determined separately not to be K_{3}-good, showing f(K_{3}, 12) = 23. In all, about 10^{9} Ramsey numbers were determined to compute f(K_{3}, 11), f(K_{3}, 12), g(K_{3}, 11) and g(K_{3}, 12) – most of them by showing that the graphs are subgraphs of another graph formerly shown to be K_{3}-good.

Problem 3 Is there always a small set S of K_{3}-good graphs of order n, such that every graph on n vertices with f(K_{3}, n) edges is contained in an element of S ?

We do not think that the cardinality of S can be bounded by a constant but it might be bounded by a moderately growing function in n.

4 Notes and Acknowledgements

We do not think that the probability for an error in a computer assisted proof is higher than one in a long proof by hand. But we think that – whenever possible – a computer assisted proof should be checked by an independent program. So although we were very careful in implementing the algorithms and checked our results against all available data, we think that an independent approach on the calculation of triangle Ramsey numbers would be an important thing to do.

Since the program was run on large clusters of different types of workstations we could not track the amount of CPU used in all cases. So we have no exact values for the total amount of CPU used. For example the accumulated CPU time for the computation of all Ramsey graphs and all maximal graphs needed to determine the graphs on 10 vertices with Ramsey number 19 was a bit less than 9 days on a mixed cluster of sun, sgi and alpha workstations and 133MHz linux PCs. The most expensive of the maximal graphs on 10 vertices with Ramsey number 23 alone took almost 22 days (distributed over the same cluster). One of the maximal graphs on 12 vertices with 49 edges and Ramsey number 23 needed 1.6 CPU years in all, the other one needed about 185 days of CPU. So the total amount of CPU used is in the range of several CPU-years. The program mtf or computer readable lists of the graphs in this article can be obtained from the authors.

We would like to thank our departments for the extensive use of their computers and especially the group of Prof. Wachsmuth at the Technische Fakultät in Bielefeld for the opportunity to run a lot of jobs on their machines. Without this support the extensive computations would not have been possible. the electronic journal of combinatorics 5 (1998), #R7 10

|H| = 3 |H| = 4 |H| = 5 |H| = 6 |H| = 7 |H| = 8 |H| = 9 |H| = 10
r = 5  1
r = 6  1
r = 7  5

r = 8

r = 9 1 18

r = 10

r = 11 2 98
r = 12  6
r = 13  2  772
r = 14  1  4  40
r = 15  9024
r = 16  13  1440
r = 17  1  19  498  242773
r = 18  1  7  119  16024
r = 19  311 10 101 711
r = 20  504
r = 21  1  28  1809 1 602 240
r = 22  22  3 155
r = 23  1  6  98  6 960

r = 24

r = 25  1  26  ?
r = 26  5  ?
r = 27  3  ?
r = 28  1  7  ?
r = 31  1  ?
r = 36  1  ?

Table 1: Numbers of connected graphs H with triangle Ramsey number r(K_{3}, H) = r.

f(K_{3}, n) g(K_{3}, n) h(K_{3}, n)
n=3  2  2  2
n=4  5  5  5
n=5  7  8  8
n=6  8  12  12
n=7  11  16  15
n=8  11  20  18
n=9  16  27  24
n=10  18  33  30
n=11  23  41
n=12  23  49
Table 2: Values for f(K_{3}, n), g(K_{3}, n) and h(K_{3}, n).

the electronic journal of combinatorics 5 (1998), #R7 11

The triangle Ramsey number for connected graphs of order 9

r(K_{3}, H) = 36 if and only if H = K_{9}. r(K_{3}, H) = 31 if and only if H = K_{9} − e. r(K_{3}, H) = 28 if and only if H^{c} is one of the graphs r(K_{3}, H) = 27 if and only if H^{c} is one of the graphs r(K_{3}, H) = 26 if and only if H^{c} is one of the graphs r(K_{3}, H) = 25 if and only if H^{c} is contained in one of the graphs and contains the graph r(K_{3}, H) = 23 if and only if H^{c} is contained in one of the graphs and contains one of the graphs the electronic journal of combinatorics 5 (1998), #R7 12 r(K_{3}, H) = 22 if and only if H^{c} is contained in one of the graphs and contains one of the graphs r(K_{3}, H) = 21 if and only if H^{c} is contained in one of the graphs and contains one of the graphs

r(K_{3}, H) = 19 if and only if H^{c} is contained in one of the graphs

and contains one of the graphs the electronic journal of combinatorics 5 (1998), #R7 14 r(K_{3}, H) = 18 if and only if H^{c} is contained in one of the graphs the electronic journal of combinatorics 5 (1998), #R7 15 the electronic journal of combinatorics 5 (1998), #R7 16 and contains one of the graphs the electronic journal of combinatorics 5 (1998), #R7 17 r(K_{3}, H) = 17 if and only if H^{c} contains one of the graphs

Extremal graphs for f(K_{3}, n) and g(K_{3}, n)

The complements of the graphs H on 10 vertices with r(K_{3}, H) = 19 and |E(H)| = g(K_{3}, 10).

The graphs H on 10 vertices with r(K_{3}, H) > 19 and |E(H)| = 19 = f(K_{3}, 10) + 1.

Two complements of graphs H on 10 vertices with r(K_{3}, H) = 19 and |E(H)| = 33 = g(K_{3}, 10) containing all graphs on 10 vertices with up to f(K_{3}, 10) = 18 edges.

The unique graph H on 11 vertices with r(K_{3}, H) > 21 and |E(H)| = 24 = f(K_{3}, 11) + 1.

Two complements of graphs H on 11 vertices with r(K_{3}, H) = 21 and |E(H)| = 41 = g(K_{3}, 11) containing all graphs on 11 vertices with up to f(K_{3}, 11) = 23 edges.

An example graph H on 12 vertices with r(K_{3}, H) > 23 and |E(H)| = 24 = f(K_{3}, 12) + 1.

Two complements of graphs H on 12 vertices with r(K_{3}, H) = 23 and |E(H)| = 49 = g(K_{3}, 12) and two complements of graphs H with r(K_{3}, H) = 23 and |E(H)| = 48 = g(K_{3}, 12) − 1 containing all graphs on 12 vertices with up to f(K_{3}, 12) = 23 edges.

References

[1] S. Brandt, Expanding graphs and Ramsey numbers, submitted.

[2] S. Brandt, G. Brinkmann, T. Harmuth, The generation of maximal triangle-free graphs, submitted.

[3] G. Brinkmann, All Ramsey numbers r(K_{3}, G) for connected graphs of order 7 and 8, to appear in Combinatorics, Probability and Computing.

[4] S. A. Burr, Ramsey numbers involving graphs with long suspended paths, J. London Math. Soc. (2) 24 (1981), 11–20.

[5] S. A. Burr, P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp, An extremal problem in generalized Ramsey theory, Ars Comb. 10 (1980), 193–203.

[6] S. A. Burr, P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp, The Ramsey number for the pair complete bipartite graph—graph of limited degree, in: Graph Theory with Applications to Algorithms and Computer Science (Alavi et. al., eds.) Wiley, 1985, 163–174.

[7] V. Chvátal, Tree—complete graph Ramsey numbers, J. Graph Theory 1 (1977), 93.

[8] R. J. Faudree, C. C. Rousseau and R. H. Schelp, All triangle—graph Ramsey numbers for connected graphs of order 6, J. Graph Theory 1 (1980), 293–300.

[9] R. J. Faudree, C. C. Rousseau and R. H. Schelp, Problems in graph theory from Memphis, in: The mathematics of Paul Erdős, Vol. II (R. L. Graham, J. Nešetřil eds.), Springer, 1996, pp. 7–26.

[10] Jin Xia, Ramsey numbers involving a triangle: theory and applications, M.Sc. thesis, Dept. of Computer Sci., Rochester institute of Technology, 1993.

[11] J. H. Kim, The Ramsey number R(3, t) has order of magnitude t^{2}/ log t, Random Structures & Algorithms 7 (1995), 173–207.

[12] B. D. McKay, Isomorph-free exhaustive generation, to appear in Journal of Algorithms.

[13] B. D. McKay, Autoson, a distributed batch system for UNIX workstations networks, Technical report TR-CS-96-03, Comp. Sci. Dept. Australian National University, 1996.

http://cs.anu.edu.au/~bdm/autoson/

[14] S. P. Radziszowski, Small Ramsey numbers, Dynamic Survey of Electronic J. Comb. (1994).

http://www.combinatorics.org/Surveys/index.html

[15] A. Schelten and I. Schiermeyer, Ramsey numbers r(K_{3}, G) for connected graphs of order seven, to appear in Discr. Appl. Math.

[16] A. Schelten and I. Schiermeyer, Ramsey numbers r(K_{3}, G) for G ≅ K_{7} − 2P_{2} and G ≅ K_{7} − 3P_{2}, to appear in Discr. Math.