The k-Ramsey number for cycles

Thumbnail Image

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

Endorsement

Review

Supplemented By

Referenced By