Study of Ramsey's number R(3,10): analysis of graphs on 40 vertices

Abstract

The Ramsey number R(k,l) is the smallest integer n such that there is no (k,l,n,e)-graph, where a (k,l,n,e)-graph denotes a graph G with n vertices and e edges and with C(G)<k e I(G)<l, where C(G) denotes the largest clique in G and I(G) denotes the largest independent set in G. The graph theory gave rise to extensive research, because no matter how simple the definition is, calculating the Ramsey numbers is an arduous task and few are known. Exoo (1989), Goedgebeur and Radziszowski (2013) showed that 40 <= R(3,10) <= 42. Thus, in this article, we will expose propositions that will be useful in the calculation of this Ramsey number. Based on the ideas of Grinstead and Roberts (1982) and Cariolaro (2007), properties and characteristics will be displayed for a bicolored graph of order 40, such that G is free of triangles, that is, C(G)<3, and does not have an independent set of order 10, that is, I(G)<10. We will show, for example, that given G = (V,E) a graph of order 40, such that C(G) < 3 and I(G) < 10, then, for every vertex v in V, we have that 4 <= deg(v) <= 9. Finally, we emphasize that the unpublished results obtained by the authors, in a research project developed at IFRS, Campus Alvorada, are found in Section 4.