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.
Copyrights © 2026