Anti-van der Waerden Numbers of Graph Products with Trees

NEW

Problem: Reconstructed conjecture (Conjecture 5.1): for finite simple connected graphs, a $k$-AP in a graph $X$ is a set admitting an ordering $v_1,\dots,v_k$ with

An exact $r$-coloring is a surjective coloring of $V(X)$, and $\operatorname{aw}(X,k)$ is the least $r$ such that every exact $r$-coloring contains a rainbow $k$-AP. A graph is $k$-peripheral if it contains $k$ vertices pairwise at distance $\operatorname{diam}(X)$. The conjecture asserts:

If $T$ is a $k$-peripheral tree and $G$ is a nontrivial connected graph, then

Result: The conjecture is false for $k=4$.

Let $T=K_{1,4}$, with center $o$ and leaves $a,b,c,d$. Then $\operatorname{diam}(T)=2$, and the four leaves are pairwise distance $2$, so $T$ is $4$-peripheral. Let $G=P_2$, with vertices $0,1$. Write $x_i=(x,i)\in V(T\square P_2)$. Distances satisfy

Color $T\square P_2$ with four colors $A,B,C,D$ by

This is an exact $4$-coloring.

Suppose a rainbow $4$-AP existed. Since $C$ and $D$ occur uniquely, it must contain both $c_1$ and $d_1$. Let its common difference be $s$. The product has diameter $3$, so $s\in\{1,2,3\}$, and $d(c_1,d_1)=2$.

If $s=1$ or $s=3$, then $c_1,d_1$ are not consecutive in the witnessing order. Hence each of the other two AP vertices is distance $s$ from either $c_1$ or $d_1$. But

all color $B$, and

also all color $B$. Thus the AP is not rainbow.

If $s=2$, then the distance-$2$ component containing $c_1,d_1$ is

Among these, the vertices other than $c_1,d_1$ all have color $A$. Thus again any $4$-AP containing $c_1,d_1$ is not rainbow.

Therefore this exact $4$-coloring has no rainbow $4$-AP, so

This contradicts the conjectured value $4$.

Citation: The conjecture and definitions are from Berikkyzy, Miller, Sprangel, Walker, and Warnberg, “Anti-van der Waerden Numbers of Graph Products with Trees,” arXiv:2310.20462, Conjecture 5.1. The counterexample above is not cited as known in the literature.