- Author
- Jan Goedgebeur (UGent) and Steven Van Overberghe (UGent)
- Organization
- Project
- Abstract
- Let R(H1, H2) denote the Ramsey number for the graphs H1,H2 , and let Jk be Kk−e. We present algorithms which enumerate all circulant and block-circulant Ramsey graphs for different types of graphs, thereby obtaining several new lower bounds on Ramsey numbers including: 49 ≤ R(K3, J12), 36 ≤ R(J4, K8 ), 52 ≤ R(K4, J8 ), 37 ≤ R(J5, J6 ), 65 ≤ R(J5, J7 ). We also use a gluing strategy to derive a new upper bound on R(J5, J6). With both strategies combined, we prove the value of two Ramsey numbers: R(J5, J6) = 37 and R(J5, J7) = 65. We also show that the 64-vertex extremal Ramsey graph for R(J5, J7 ) is unique. Furthermore, our algorithms also allow to establish new lower bounds and exact values on Ramsey numbers involving wheel graphs and complete bipartite graphs, including: R(W7, W4) = 21, R(W7, W7) = 19, R(K3,4 , K 3,4) = 25 and R(K3,5 , K3,5) = 33.
- Keywords
- Applied Mathematics, Discrete Mathematics and Combinatorics, Ramsey number, (Block-)circulant graph, Almost-complete graph, Wheel graph, Computation
Downloads
-
(...).pdf
- full text (Published version)
- |
- UGent only
- |
- |
- 404.11 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU-8739377
- MLA
- Goedgebeur, Jan, and Steven Van Overberghe. “New Bounds for Ramsey Numbers R(Kk−e,Kl−e).” DISCRETE APPLIED MATHEMATICS, vol. 307, 2022, pp. 212–21, doi:10.1016/j.dam.2021.10.023.
- APA
- Goedgebeur, J., & Van Overberghe, S. (2022). New bounds for Ramsey numbers R(Kk−e,Kl−e). DISCRETE APPLIED MATHEMATICS, 307, 212–221. https://doi.org/10.1016/j.dam.2021.10.023
- Chicago author-date
- Goedgebeur, Jan, and Steven Van Overberghe. 2022. “New Bounds for Ramsey Numbers R(Kk−e,Kl−e).” DISCRETE APPLIED MATHEMATICS 307: 212–21. https://doi.org/10.1016/j.dam.2021.10.023.
- Chicago author-date (all authors)
- Goedgebeur, Jan, and Steven Van Overberghe. 2022. “New Bounds for Ramsey Numbers R(Kk−e,Kl−e).” DISCRETE APPLIED MATHEMATICS 307: 212–221. doi:10.1016/j.dam.2021.10.023.
- Vancouver
- 1.Goedgebeur J, Van Overberghe S. New bounds for Ramsey numbers R(Kk−e,Kl−e). DISCRETE APPLIED MATHEMATICS. 2022;307:212–21.
- IEEE
- [1]J. Goedgebeur and S. Van Overberghe, “New bounds for Ramsey numbers R(Kk−e,Kl−e),” DISCRETE APPLIED MATHEMATICS, vol. 307, pp. 212–221, 2022.
@article{8739377,
abstract = {{Let R(H1, H2) denote the Ramsey number for the graphs H1,H2 , and let Jk be Kk−e. We present algorithms which enumerate all circulant and block-circulant Ramsey graphs for different types of graphs, thereby obtaining several new lower bounds on Ramsey numbers including: 49 ≤ R(K3, J12), 36 ≤ R(J4, K8 ), 52 ≤ R(K4, J8 ), 37 ≤ R(J5, J6 ), 65 ≤ R(J5, J7 ). We also use a gluing strategy to derive a new upper bound on R(J5, J6). With both strategies combined, we prove the value of two Ramsey numbers: R(J5, J6) = 37 and R(J5, J7) = 65. We also show that the 64-vertex extremal Ramsey graph for R(J5, J7 ) is unique. Furthermore, our algorithms also allow to establish new lower bounds and exact values on Ramsey numbers involving wheel graphs and complete bipartite graphs, including: R(W7, W4) = 21, R(W7, W7) = 19, R(K3,4 , K 3,4) = 25 and R(K3,5 , K3,5) = 33.}},
author = {{Goedgebeur, Jan and Van Overberghe, Steven}},
issn = {{0166-218X}},
journal = {{DISCRETE APPLIED MATHEMATICS}},
keywords = {{Applied Mathematics,Discrete Mathematics and Combinatorics,Ramsey number,(Block-)circulant graph,Almost-complete graph,Wheel graph,Computation}},
language = {{eng}},
pages = {{212--221}},
title = {{New bounds for Ramsey numbers R(Kk−e,Kl−e)}},
url = {{http://doi.org/10.1016/j.dam.2021.10.023}},
volume = {{307}},
year = {{2022}},
}
- Altmetric
- View in Altmetric
- Web of Science
- Times cited: