Anti-van der Waerden numbers of graph products with trees
Abstract
Given a graph G, an exact r-coloring of G is a surjective function c : V(G) → [1, …, r]. An arithmetic progression in G of length j with common difference d is a set of vertices {v1, …, vj} such that d(vi, vi+1) = d for 1 ≤ i < j. An arithmetic progression is rainbow if all of the vertices are colored distinctly. The fewest number of colors that guarantees a rainbow arithmetic progression of length three is called the anti-van der Waerden number of G and is denoted aw(G, 3). It is known that for any connected graphs G and H on two or more vertices we have 3 ≤ aw(G □ H, 3) ≤ 4. A tree is called 3-peripheral if it has three vertices that are pairwise diameter distance from one another. In this work we determine that aw(G □ T, 3) = 3 when T is 3-peripheral and G is any connected graph with |G| ≥ 2. We also determine that aw(T □ T′, 3) = 4 when T and T′ are not 3-peripheral and diam(T □ T′) is odd.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2026.14.2.2
References
M. Axenovich and D. Fon-Der-Flaass, On rainbow arithmetic progressions, Electron. J. Combin. 11 (1) (2004), Research Paper 1, 7pp. https://doi.org/10.37236/1754
M. Axenovich and R. R. Martin, Sub-Ramsey numbers for arithmetic progressions, Graphs Combin. 22 (1) (2006), 297–309. https://doi.org/10.1007/s00373-006-0663-2
Z. Berikkyzy, J. Miller, and N. Warnberg. Full classification of anti-van der Waerden numbers of graph products of forests, Australas. J. Combin. 94 (1) (2026), 201–220. https://ajc.maths.uq.edu.au/?page=get_volumes&volume=94
Z. Berikkyzy, A. Schulte, E. Sprangel, S. Walker, N. Warnberg, and M. Young, Anti-van der Waerden numbers on Graphs, Graphs Combin. 38 (124) (2022). https://doi.org/10.1007/s00373-022-02516-9
Z. Berikkyzy, A. Schulte, and M. Young, Anti-van der Waerden numbers of 3-term arithmetic progressions, Electron. J. Combin. 24 (2) (2017), Paper 2.39, 9 pp. https://doi.org/10.37236/6101
E. Bevilacqua, A. King, J. Kritschgau, M. Tait, S. Tebon and M. Young, Rainbow numbers for x1 + x2 = kx3 in ℤn, Integers 20 (2020), A50. http://math.colgate.edu/~integers/vol20.html
M. Budden, Schur numbers involving rainbow colorings, Ars Math. Contemp. 18 (2020), 281–288. https://doi.org/10.26493/1855-3974.2019.30b
M. Budden and W. Stiles, Anti-Ramsey hypergraph numbers, Electron. J. Graph Theory Appl. 9 (2) (2021), 397–407. https://dx.doi.org/10.5614/ejgta.2021.9.2.12
S. Butler, C. Erickson, L. Hogben, K. Hogenson, L. Kramer, R. L. Kramer, J. Lin, R. R. Martin, D. Stolee, N. Warnberg, and M. Young, Rainbow arithmetic Progressions, J. Comb. 7 (4) (2016), 595–626. https://dx.doi.org/10.4310/JOC.2016.v7.n4.a3
P. Erdős, M. Simonovits, and V. Sós Anti-Ramsey theorems, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday) II (1973), 633–643. https://catalog.lib.uchicago.edu/vufind/Record/56681
K. Fallon, C. Giles, H. Rehm, S. Wagner and N. Warnberg, Rainbow numbers of [n] for ∑i=1k−1 xi = xk, Australas. J. Combin. 77 (1) (2020), 1–8. https://ajc.maths.uq.edu.au/pdf/77/ajc_v77_p001.pdf
M. Huicochea and A. Montejano, The Structure of Rainbow-Free Colorings For Linear Equations on Three Variables in ℤp, Integers 15A (2015), A8. http://math.colgate.edu/~integers/vol15a.html
V. Jungić, J. Licht (Fox), M. Mahdian, J. Nešetřil, and R. Radoičić, Rainbow arithmetic progressions and anti-Ramsey results, Combin. Probab. Comput. 12 (5-6) (2003), 599–620. https://doi.org/10.1017/S096354830300587X
B. Llano and A. Montejano, Rainbow-free colorings of x + y = cz in ℤp, Discrete Math. 312, (2012), 2566–2573. https://doi.org/10.1016/j.disc.2011.09.005
J. Miller and N. Warnberg, Anti-van der Waerden Number of Graph Products of Cycles. Australas. J. Combin. 87 (1) (2023), 24–40. https://ajc.maths.uq.edu.au/?page=get_volumes&volume=87
F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1928), 264–286. https://doi.org/10.1112/plms/s2-30.1.264
H. Rehm, A. Schulte and N. Warnberg, Anti-van der Waerden numbers on graph products, Australas. J. Combin. 73 (3) (2019), 486–500. https://ajc.maths.uq.edu.au/?page=get_volumes&volume=73
I. Schur, Über Potenzreihen die im Innern des Einheitskreises beschränkt sind, J. Reine Angew. Math (1917), 205–232.
K. Uherka, An introduction to Ramsey theory and anti-Ramsey theory on the integers, Master's Creative Component Iowa State University (2013).
B. van der Waerden, Beweis einer baudetschen vermutung, Nieuw Arch. Wisk. 19 (1927), 212–216.
M. Young, Rainbow arithmetic progressions in finite Abelian groups, J. Comb. 9 (4) (2018), 619–629. https://dx.doi.org/10.4310/JOC.2018.v9.n4.a3
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.