Abstract
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 \({\overline{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 \le t\), then \(R(K_4-e,K_ {s+t+1}) \ge 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bohman, T., Keevash, P.: Dynamic concentration of the triangle-free process. In: The Seventh European Conference on Combinatorics, Graph Theory and Applications, pp. 489–495. Springer (2013)
Burr, S.A., Erdos, P., Faudree, R.J., Schelp, R.: On the difference between consecutive Ramsey numbers. Util. Math. 35, 115–118 (1989)
Gyárfás, A., Sebő, A., Trotignon, N.: The chromatic gap and its extremes. J. Comb. Theory Ser. B 102(5), 1155–1178 (2012)
Jiang, Y., Liang, M., Teng, Y., Xu, X.: The cyclic triangle-free process. Symmetry 11(8), 955 (2019)
Liang, M., Radziszowski, S.P., Xu, X.: On a diagonal conjecture for classical Ramsey numbers. Discrete Appl. Math. 267, 195–200 (2019)
Lidickỳ, B., Pfender, F.: Semidefinite programming and Ramsey numbers. arXiv preprint arXiv:1704.03592 (2017)
Pontiveros, G.F., Griffiths, S., Morris, R.: The triangle-free process and R(3, k). arXiv preprint arXiv:1302.6279118 (2013)
Pontiveros, G.F., Griffiths, S., Morris, R.: The Triangle-Free Process and the Ramsey Number R(3, k). American Mathematical Society, Washington, DC (2020)
Radziszowski, S.P.: Small Ramsey numbers. In: The Electronic Journal of Combinatorics pp. DS1–Mar (2017)
Shearer, J.B.: A note on the independence number of triangle-free graphs. Discrete Math. 46(1), 83–87 (1983)
Xiaodong, X., Zheng, X., Radziszowski, S.P.: A constructive approach for the lower bounds on the Ramsey numbers R(s, t). J. Graph Theory 47(3), 231–239 (2004)
Xu, X., Shao, Z., Radziszowski, S.P.: More constructive lower bounds on classical Ramsey numbers. SIAM J. Discrete Math. 25(1), 394–400 (2011)
Zhu, R., Xu, X., Radziszowski, S.P.: A small step forwards on the Erdős–Sós problem concerning the Ramsey numbers R(3, k). Discrete Appl. Math. 214, 216–221 (2016)
Acknowledgements
This research was partially supported by the National Natural Science Foundation of China awards (61572005, 11361008).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Jiang, Y., Liang, M., Sun, Y. et al. On Ramsey Numbers \(R(K_4-e, K_t)\). Graphs and Combinatorics 37, 651–661 (2021). https://doi.org/10.1007/s00373-020-02262-w
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-020-02262-w