Total Difference Chromatic Numbers of Regular Infinite Graphs

NEW

Problem: For simple undirected graphs, a proper $k$-total difference labeling of $G$ is a map

such that for every edge $uv$,

adjacent vertices receive distinct labels, incident edges receive distinct labels, and no edge has the same label as either endpoint. Let $\chi_{td}(G)$ be the least such $k$. The question asks whether there is a function $f(x,y)$ such that

for all graphs $G_1,G_2$ with finite total difference chromatic numbers.

Result: Yes. One may take

It suffices to prove the asymmetric bound

where $a=\chi_{td}(G_1)$, $b=\chi_{td}(G_2)$; swapping the factors gives the stated symmetric bound.

Let $\ell_1,\ell_2$ be proper total difference labelings of $G_1,G_2$ using labels in $[a]$, $[b]$. Put $B=b+1$, and label each vertex $(u,v)\in V(G_1\square G_2)$ by

Then

For an edge in the $G_1$-direction, $(u,v)(u',v)$, define

For an edge in the $G_2$-direction, $(u,v)(u,v')$, define

Now check properness. Vertex labels differ on adjacent vertices because $\ell_1,\ell_2$ are proper. Incident $G_1$-direction edge labels are distinct since they are $B$ times distinct incident edge labels of $G_1$. Incident $G_2$-direction edge labels are distinct by properness in $G_2$. A $G_1$-direction edge label is a positive multiple of $B=b+1$, while a $G_2$-direction edge label is at most $b-1$, so mixed incident edges have distinct labels.

Finally, no edge label equals an endpoint label. A $G_1$-direction edge label is divisible by $B$, whereas every vertex label has residue $\ell_2(v)\in\{1,\dots,b\}$ modulo $B$. A $G_2$-direction edge label is $\ell_2(vv')$; if $\ell_1(u)=1$, endpoint labels are $\ell_2(v),\ell_2(v')$, and properness of $\ell_2$ excludes equality; if $\ell_1(u)>1$, endpoint labels exceed $b+1$, while $\ell_2(vv')\le b-1$.

Thus $L$ is a proper $(ab+a-1)$-total difference labeling of $G_1\square G_2$. Hence the desired bounding function exists.

Citation: The problem and definitions are from Benson-Tilsen, Brock, Faunce, Kumar, Stein, and Zelinsky, “Total Difference Labeling of Regular Infinite Graphs,” arXiv:2107.11706, Question 19. The explicit product bound above is the resolution.