×

Subgraph counting identities and Ramsey numbers. (English) Zbl 0869.05043

For each vertex \(v\) of a graph \(G\), the number of subgraphs of each isomorphism class which lie in the neighbourhood or complementary neighbourhood of \(v\) is considered. These numbers, summed over \(v\), are shown to satisfy a series of identities. Using these, it is shown that \(R(5,5)\leq 49\) and \(R(4,6)\leq 41\), where \(R(m,n)\) is the usual Ramsey number. The authors also give some experimental evidence to support their conjecture that \(R(5,5)= 43\).

MSC:

05C55 Generalized Ramsey theory
05C30 Enumeration in graph theory

Keywords:

Ramsey number

Software:

Maple; LINDO
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] H. L. Abbott, 1965, Some Problems in Combinatorial Analysis, University of Alberta, Edmonton; H. L. Abbott, 1965, Some Problems in Combinatorial Analysis, University of Alberta, Edmonton
[2] Char, B. W.; Geddes, K. O.; Gonnet, G. H.; Monagan, M. B.; Watt, S. M., MAPLE Reference Manual (1990), WATCOM: WATCOM Waterloo · Zbl 0758.68038
[3] Erdős, P.; Lovász, L.; Spencer, J., Strong independence of graphcopy functions, Graph Theory and Related Topics (1979), Academic Press: Academic Press New York · Zbl 0462.05057
[4] Exoo, G., A lower bound for \(R\), J. Graph Theory, 13, 97-98 (1989) · Zbl 0661.05044
[5] Exoo, G., On the Ramsey numbers \(RRR\), Ars Combinatoria, 35, 1-10 (1993)
[6] Giraud, G. R., Une majoration du nombre de Ramsey binaire-bicolore en (5,5), C. R. Acad. Sci. Paris, 265, 809-811 (1967) · Zbl 0185.03101
[7] Goodman, A. W., On sets of acquaintances and strangers at any party, Amer. Math. Monthly, 66, 778-783 (1959) · Zbl 0092.01305
[8] R. W. Irving, 1973, Contributions to Ramsey Theory, University of Glasgow; R. W. Irving, 1973, Contributions to Ramsey Theory, University of Glasgow
[9] Kalbfleisch, J. G., Construction of special edge-chromatic graphs, Canad. Math. Bull., 8, 575-584 (1965) · Zbl 0132.21205
[10] J. G. Kalbfleisch, 1966, Chromatic Graphs and Ramsey’s Theorem, University of Waterloo; J. G. Kalbfleisch, 1966, Chromatic Graphs and Ramsey’s Theorem, University of Waterloo
[11] Kalbfleisch, J. G., Upper bounds for some Ramsey numbers, J. Combin. Theory, 2, 35-42 (1967) · Zbl 0149.41406
[12] Kocay, B., An extension of Kelly’s lemma to spanning subgraphs, Congr. Numer., 31, 109-120 (1981) · Zbl 0516.05043
[13] McKay, B. D., Technical report TR-CS-90-02 (1990)
[14] McKay, B. D., Technical Report TR-CS-96-03 (1996)
[15] McKay, B. D.; Radziszowski, S. P., A new upper bound for the Ramsey number \(R\), Australasian J. Combin, 5, 13-20 (1992) · Zbl 0769.05067
[16] McKay, B. D.; Radziszowski, S. P., Linear programming in some Ramsey problems, J. Combin. Theory Ser. B, 61, 125-132 (1994) · Zbl 0811.05047
[17] McKay, B. D.; Radziszowski, S. P., \(R\), J. Graph Theory, 19, 309-322 (1995) · Zbl 0822.05050
[18] McKay, B. D.; Zhang, K. M., The value of the Ramsey number \(R\), J. Graph Theory, 16, 99-105 (1992) · Zbl 0758.05098
[19] NAG Fortran Library (1993), NAG: NAG Oxford
[20] Radziszowski, S. P., Small Ramsey numbers, Electronic J. Combin., Dynamic Survey, 1 (1994-6)
[21] Radziszowski, S. P.; Kreher, D. L., On \(Rk\), J. Combin. Math. Combin. Comput., 4, 37-52 (1988) · Zbl 0683.05031
[22] Schrage, L. E., User’s Manual for LINDO (1981), The Scientific Press: The Scientific Press Palo Alto
[23] Thomason, A. G., On finite Ramsey numbers, European J. Combin., 3, 263-273 (1982) · Zbl 0503.05046
[24] Walker, K., Dichromatic graphs and Ramsey numbers, J. Combin. Theory, 5, 238-243 (1968) · Zbl 0191.22601
[25] Walker, K., An upper bound for the Ramsey number \(M\), J. Combin. Theory, 11, 1-10 (1971) · Zbl 0225.05117
[26] Whitney, H., The colouring of graphs, Ann. Math., 33, 688-718 (1932) · JFM 58.0606.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.