On Small Balanceable, Strongly-Balanceable and Omnitonal Graphs

Abstract

In Ramsey Theory for graphs we are given a graph G and we are required to find the least n0 such that, for any n ≥ n0, any red/blue colouring of the edges of Kn gives a subgraph G all of whose edges are blue or all are red. Here we shall be requiring that, for any red/blue colouring of the edges of Kn, there must be a copy of G such that its edges are partitioned equally as red or blue (or the sizes of the colour classes differs by one in the case when G has an odd number of edges). This introduces the notion of balanceable graphs and the balance number of G which, if it exists, is the minimum integer bal(n, G) such that, for any red/blue colouring of E(Kn) with more than bal(n, G) edges of either colour, Kn will contain a balanced coloured copy of G as described above. The strong balance number sbal(n, G) is analogously defined when G has an odd number of edges, but in this case we require that there are copies of G with both one more red edge and one more blue edge.

Keywords

• edge-colouring
• zero-sum ramsey
• balanceable graphs
• omnitonal graphs
• 05c15
• 05c55