Search

Let G and H be finite undirected graphs. The Ramsey number R(G, H) is the smallest integer n such that for every graph F of order n, either F contains a subgraph isomorphic to G or its complement F ¯ contains a subgraph isomorphic to H. An (s, t)-graph is a graph that contains neither a clique of order s nor an independent set of order t. In this paper we obtain some inequalities involving Ramsey numbers of the form R (K 4 - e , K t) . In particular, a constructive proof implies that if G is a (k , s + 1) -graph, H is a (k , t + 1) -graph, and both G and H contain a (K k - e) -free graph M as an induced subgraph, then we have R (K k + 1 - e , K s + t + 1) > | V (G) | + | V (H) | + | V (M) |. Furthermore, if s ≤ t , then R (K 4 - e , K s + t + 1) ≥ R (3 , s + 1) + R (3 , t + 1) + s . In the experimental part, we use the (K 4 - e) -free graph generation process to construct graphs witnessing lower bounds for R (K 4 - e , K t) , and compare the results obtained by this approach to the results obtained by analogous triangle-free process. Finally, some open problems involving Ramsey numbers of the form R (K 4 - e , K t) and their asymptotics are posed. [ABSTRACT FROM AUTHOR]