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