Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 14, No 2 (2026): Electronic Journal of Graph Theory and Applications

Anti-van der Waerden numbers of graph products with trees

Zhanar Berikkyzy (Mathematics Department, Fairfield University)
Joe Miller (Department of Mathematics, Iowa State University)
Elizabeth Sprangel (Health and Human Services Department, Hennepin County)
Shanise Walker (Department of Mathematical Sciences, Clark Atlanta University)
Nathan Joel Warnberg (Department of Mathematics and Statistics, University of Wisconsin-La Crosse)



Article Info

Publish Date
29 Oct 2026

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.

Copyrights © 2026






Journal Info

Abbrev

ejgta

Publisher

Subject

Electrical & Electronics Engineering

Description

The Electronic Journal of Graph Theory and Applications (EJGTA) is a refereed journal devoted to all areas of modern graph theory together with applications to other fields of mathematics, computer science and other sciences. The journal is published by the Indonesian Combinatorial Society ...