The k-Ramsey number for cycles

dc.contributor.authorMaartens, Ronald John
dc.date.accessioned2023-05-08T08:18:49Z
dc.date.available2023-05-08T08:18:49Z
dc.date.issued2022
dc.descriptionA 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.abstractLet ๐น 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.librarianNG (2023)
dc.facultyFaculty of Science
dc.identifier.urihttps://hdl.handle.net/10539/35482
dc.language.isoen
dc.phd.titlePhD
dc.schoolSchool of Mathematics
dc.titleThe k-Ramsey number for cycles
dc.typeThesis
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
1779477_R_J_Maartens_PhD_Thesis.pdf
Size:
870.19 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.43 KB
Format:
Item-specific license agreed upon to submission
Description:
Collections