The k-Ramsey number for cycles

Date
2022
Authors
Maartens, Ronald John
Journal Title
Journal ISSN
Volume Title
Publisher
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 โ‰ค ๐‘˜ < ๐‘›.
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
Keywords
Citation
Collections