1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

On Small Balanceable, Strongly-Balanceable and Omnitonal Graphs

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1219 - 1235
Received: 22 Aug 2019
Accepted: 02 Jun 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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 nn0, 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.

These parameters were introduced by Caro, Hansberg and Montejano. These authors also introduce the more general omnitonal number ot(n, G) which requires copies of G containing a complete distribution of the number of red and blue edges over E(G).

In this paper we shall catalogue bal(n, G), sbal(n, G) and ot(n, G) for all graphs G on at most four edges. We shall be using some of the key results of Caro et al. which we here reproduce in full, as well as some new results which we prove here. For example, we shall prove that the union of two bipartite graphs with the same number of edges is always balanceable.

Keywords

MSC 2010

[1] C. Augspurger, M. Minter, K. Shoukry, P. Sissokho and K. Voss, Avoiding zero-sum subsequences of prescribed length over the integers (2016). arXiv:1603.03978 Search in Google Scholar

[2] A. Berger, An analogue of the Erdős-Ginzburg-Ziv theorem over 𝕑, Discrete Math. 342 (2019) 815–820. https://doi.org/10.1016/j.disc.2018.11.018 Search in Google Scholar

[3] B. Bollobás, Extremal Graph Theory (Courier Corporation, 2004). Search in Google Scholar

[4] M. Bowen, A. Hansberg, A. Montejano and A. Müyesser, Colored unavoidable patterns and balanceable graphs (2019). arXiv:1912.06302 Search in Google Scholar

[5] Y. Caro, A. Hansberg and A. Montejano, Amoebas (2019), in preparation. Search in Google Scholar

[6] Y. Caro, A. Hansberg and A. Montejano, Unavoidable chromatic patterns in 2-colorings of the complete graph (2019). arXiv:1810.12375 Search in Google Scholar

[7] Y. Caro, A. Hansberg and A. Montejano, Zero-sum Km over 𝕑 and the story of K4, Graphs Combin. 35 (2019) 855–865. https://doi.org/10.1007/s00373-019-02040-3 Search in Google Scholar

[8] Y. Caro, A. Hansberg and A. Montejano, Zero-sum subsequences in bounded-sum {−1, 1}-sequences, J. Combin. Theory Ser. A 161 (2019) 387–419. https://doi.org/10.1016/j.jcta.2018.09.001 Search in Google Scholar

[9] Y. Caro and R. Yuster, On zero-sum and almost zero-sum subgraphs over 𝕑, Graphs Combin. 32 (2016) 49–63. https://doi.org/10.1007/s00373-015-1541-6 Search in Google Scholar

[10] E.J. Cockayne and P.J. Lorimer, The Ramsey number for stripes, J. Aust. Math. Soc. 19 (1975) 252–256. https://doi.org/10.1017/S1446788700029554 Search in Google Scholar

[11] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Hungar. 10 (1959) 337–356. https://doi.org/10.1007/BF02024498 Search in Google Scholar

[12] R.J. Faudree and R.H. Schelp, All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974) 313–329. https://doi.org/10.1016/0012-365X(74)90151-4 Search in Google Scholar

[13] Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in: Erdős Centennial, Bolyai Soc. Math. Stud. 25, L. Lovász, I.Z. Ruzsa and V.T. Sós (Ed(s)), (Springer, Berlin, Heidelberg, 2013) 169–264. https://doi.org/10.1007/978-3-642-39286-3_7 Search in Google Scholar

[14] A. Girão and B. Narayanan, Turán theorems for unavoidable patterns (2019). arXiv:1907.00964 Search in Google Scholar

[15] O. Pikhurko, A note on the Turán function of even cycles, Proc. Amer. Math. Soc. 140 (2012) 3687–3692. https://doi.org/10.1090/S0002-9939-2012-11274-2 Search in Google Scholar

[16] A. Robertson, Zero-sum analogues of van der Waerden’s theorem on arithmetic progressions, J. Comb. 11 (2020) 231–248. https://doi.org/10.4310/JOC.2020.v11.n2.a1 Search in Google Scholar

[17] A. Robertson, Zero-sum generalized Schur numbers (2018). arXiv:1802.03382 Search in Google Scholar

[18] A. Sun, Zero-sum subsequences in bounded-sum {−r, s}-sequences (2019). arXiv:1907.06623 Search in Google Scholar

[19] D.B. West, Introduction to Graph Theory (Math. Classics, Pearson, 2017). Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo