Geodesic
On Small Balanceable, Strongly-Balanceable and Omnitonal Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1219-1235.

Voir la notice de l'article provenant de la source Library of Science

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. 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: edge-colouring, zero-sum Ramsey, balanceable graphs, omnitonal graphs 
@article{DMGT_2022_42_4_a12,
     author = {Caro, Yair and Lauri, Josef and Zarb, Christina},
     title = {On {Small} {Balanceable,} {Strongly-Balanceable} and {Omnitonal} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1219--1235},
     publisher = {mathdoc},
     volume = {42},
     number = {4},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a12/}
}
TY  - JOUR
AU  - Caro, Yair
AU  - Lauri, Josef
AU  - Zarb, Christina
TI  - On Small Balanceable, Strongly-Balanceable and Omnitonal Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1219
EP  - 1235
VL  - 42
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a12/
LA  - en
ID  - DMGT_2022_42_4_a12
ER  - 
%0 Journal Article
%A Caro, Yair
%A Lauri, Josef
%A Zarb, Christina
%T On Small Balanceable, Strongly-Balanceable and Omnitonal Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1219-1235
%V 42
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a12/
%G en
%F DMGT_2022_42_4_a12
Caro, Yair; Lauri, Josef; Zarb, Christina. On Small Balanceable, Strongly-Balanceable and Omnitonal Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1219-1235. http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a12/

[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

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

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

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

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

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

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

[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

[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

[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

[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

[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

[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

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

[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

[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

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

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

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