Ramsey numbers for graphs with five vertices
β Scribed by George R. T. Hendry
- Publisher
- John Wiley and Sons
- Year
- 1989
- Tongue
- English
- Weight
- 147 KB
- Volume
- 13
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
β¦ Synopsis
The Ramsey numbers d f , , F2) are tabulated for essentially all but six pairs of graphs F, and F2 with five vertices.
For isolate-free graphs F, and F2, the Ramsey number r(F,, FJ is the least positive integerp such that, for every graph G with p vertices, either F, is a subgraph of G or F, is a subgraph of c. Chvatal and Harary [4,5] determined all Ramsey numbers for graphs with at most four vertices. Clancy [6] extended this work by determining r(F,, F,) for all but five pairs of graphs F, and F, of orders five and at most four, respectively. Four of the missing numbers have since been evaluated-one by Bolze and Harborth [ l ] , one by Exoo, Harborth, and Mengersen [lo] and two by Hendry [17]. This leaves only one undetermined number in Clancy's table for which the best bounds known to the author are 25 r ( K 5 , K 4 ) 28 [18,25]. The object of the present paper is to tabulate the Ramsey numbers of graphs with exactly five vertices. Since one of the seven numbers not explicitly determined in Table 1 is equal to r(K5,K4), there are essentially only six numbers missing from this table. The 23 isolate-free graphs of order five are labeled G , , . . . , G,, as in [6], see Figure 1.
The detailed proofs of our results are inevitably rather lengthy and it is not appropriate that they should appear here (although they are available from the author on request). The list of references has been limited to those works specifically referred to in the proofs and we apologize in advance for any omissions.
π SIMILAR VOLUMES
## Abstract Let __R__(__G__) denote the minimum integer __N__ such that for every bicoloring of the edges of __K~N~__, at least one of the monochromatic subgraphs contains __G__ as a subgraph. We show that for every positive integer __d__ and each Ξ³,0β<βΞ³β<β1, there exists __k__β=β__k__(__d__,Ξ³) su
A graph \(G\) of order \(n\) is \(p\)-arrangeable if its vertices can be ordered as \(v_{1}, v_{2}, \ldots, v_{n}\) such that \(\left|N_{L_{i}}\left(N_{R_{i}}\left(v_{i}\right)\right)\right| \leqslant p\) for each \(1 \leqslant i \leqslant n-1\), where \(L_{i}=\left\{v_{1}, v_{2}, \ldots, v_{i}\righ
## Abstract The irredundant Ramsey number __s(m, n)__ is the smallest p such that in every twoβcoloring of the edges of __K~p~__ using colors red (__R__) and blue (__B__), either the blue graph contains an __m__βelement irredundant set or the red graph contains an __n__βelement irredundant set. We