Balanceability and omnitonality of graphs with five edges

Abstract

A series of publications by Yair Caro and others on an extension of the party problem — a classic problem in Ramsey Theory — explores the presence of particular 2-edge-colourings of any graph — not just monochromatic copies of a complete subgraph — contained in an arbitrary 2-edge-colouring of the complete graph. Using this particular extension, a set of graph properties is defined, those being balanceability, strong balanceability, and omnitonality. This dissertation aims to investigate these three properties for graphs with five edges to give a quasi-complete classification from both given results and original work. The research done here is organised as follows. The first chapter provides introductory context to the problem at hand along with some definitions that may be required in further chapters. The second chapter is a quick detour into Zero-Sum Ramsey Theory which explores the background research into Zero-Sum Ramsey numbers that lead up to the current work on red/blue-edge-colourings of the complete graph. This chapter includes the definition of the graph properties to be investigated, along with a review of the classification of total omnitonality of graphs given by Caro, Lauri, and Zarb in [10]. The third chapter explores and investigates the omnitonality of graphs with five edges by providing a classification from various results given and proved by Caro and others. The fourth chapter tackles the strong balanceability of graphs with five edges through both classification from previous results given and proved by others, along with three original constructions, two of which are an adaptation of a procedure from [11]. The fifth chapter provides a full classification of balanceability of graphs with five edges using previous results but also through a plethora of original constructive proofs which are a similar adaptation of a procedure from [11]. The sixth and final chapter provides a collection of all the work in classification done in the previous chapters, along with conjectures and guidelines on how a full classification may be achieved.