𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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


Irredundant ramsey numbers for graphs
✍ R. C. Brewster; E. J. Cockayne; C. M. Mynhardt πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 356 KB
On graphs with linear Ramsey numbers
✍ R. L. Graham; V. RΓΆdl; A. RuciΕ„ski πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 141 KB πŸ‘ 1 views
On graphs with small Ramsey numbers
✍ A. V. Kostochka; V. RΓΆdl πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 88 KB

## 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

Graphs with Linearly Bounded Ramsey Numb
✍ G.T. Chen; R.H. Schelp πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 439 KB

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

CO-irredundant Ramsey numbers for graphs
✍ E. J. Cockayne; G. MacGillivray; J. Simmons πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 120 KB πŸ‘ 2 views
On irredundant Ramsey numbers for graphs
✍ Johannes H. Hattingh πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 248 KB

## 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