The k-Ramsey number for cycles
| dc.contributor.author | Maartens, Ronald John | |
| dc.date.accessioned | 2023-05-08T08:18:49Z | |
| dc.date.available | 2023-05-08T08:18:49Z | |
| dc.date.issued | 2022 | |
| dc.description | A thesis submitted in fulfillment of the requirements for the degree of Doctor of Philosophy to the Faculty of Science, School of Mathematics, University of the Witwatersrand, Johannesburg, 2022 | |
| dc.description.abstract | Let 𝐹 and 𝐻 be two graphs. The Ramsey number 𝑅(𝐹, 𝐻) is defined as the smallest positive integer 𝑛 such that for any red-blue coloring of the edges of 𝐾𝑛 there is a subgraph of 𝐾𝑛 isomorphic to 𝐹 whose edges are all colored red, or a subgraph of 𝐾𝑛 isomorphic to 𝐻 whose edges are all colored blue. Let 𝐹 and 𝐻 now be two bipartite graphs with Ramsey number 𝑅(𝐹, 𝐻). Further, let 𝐺 be a complete 𝑘-partite graph 𝐾𝑛1,𝑛2,...,𝑛𝑘 of order 𝑛 = ∑ 𝑛𝑖 𝑘 𝑖=1 with 𝑛𝑖 ∈ {⌈𝑛 𝑘⁄ ⌉, ⌊𝑛 𝑘⁄ ⌋} for 𝑖 = 1, ... , 𝑘 and 𝑘 = 2, ... , 𝑅(𝐹, 𝐻). The 𝑘-Ramsey number 𝑅𝑘(𝐹, 𝐻) is then defined as the smallest positive integer 𝑛 such that for any red- blue coloring of the edges of 𝐺 there is a subgraph of 𝐺 isomorphic to 𝐹 whose edges are all colored red, or a subgraph of 𝐺 isomorphic to 𝐻 whose edges are all colored blue. The 𝑘-Ramsey number 𝑅𝑘(𝐹, 𝐻) is defined in [2] for two bipartite graphs 𝐹 and 𝐻 only. In the thesis we investigate the 𝑘-Ramsey number of two cycles which are not both bipartite. Amongst other results, we determine 𝑅𝑘(𝐶3, 𝐶4), 𝑅𝑘(𝐶3, 𝐶5), 𝑅𝑘(𝐶4, 𝐶5) and 𝑅𝑘(𝐶5, 𝐶5) for all the possible values of 𝑘 in each case. From these results and others, we conclude with a conjecture regarding the formula for 𝑅𝑘(𝐶2𝑛+1, 𝐶2𝑚+1) where 𝑛 ≥ 𝑚 ≥ 1, (𝑛, 𝑚) ≠ (1,1) and 𝑘 = 5, ... ,4𝑛 + 1. We show that 𝑅2(𝐹, 𝐻) does not exist when 𝐹 is nonbipartite and 𝐻 is a nonempty graph. We also show that 𝑅𝑘(𝐾𝑛, 𝐻) does not exist when 𝐻 is a nonempty graph and 2 ≤ 𝑘 < 𝑛. | |
| dc.description.librarian | NG (2023) | |
| dc.faculty | Faculty of Science | |
| dc.identifier.uri | https://hdl.handle.net/10539/35482 | |
| dc.language.iso | en | |
| dc.phd.title | PhD | |
| dc.school | School of Mathematics | |
| dc.title | The k-Ramsey number for cycles | |
| dc.type | Thesis |