An Extension on Neighbor Sum Distinguishing Total Coloring of Graphs

NEW

Problem: For a finite simple connected graph $G$, let a non-proper total $k$-coloring be a map

For $v\in V(G)$, define its full sum

The coloring is neighbor full sum distinguishing if $\Phi_f(u)\ne \Phi_f(v)$ for every edge $uv$. The parameter $fgndi_{\sum}(G)$ is the least such $k$. The target conjecture asks whether

for every connected graph $G$ with maximum degree $\Delta(G)=3$. This reconstruction follows directly from the paper abstract and the stated Problem 1.

Result: The conjecture is true.

Work over $\mathbb F_3$. Let $B$ be the ordinary vertex-edge incidence matrix of $G$ over $\mathbb F_3$, so

First observe the following. If there is a proper vertex coloring

with $\alpha\in \operatorname{im} B$, then $fgndi_{\sum}(G)\le 3$. Indeed choose $x\in \mathbb F_3^{E(G)}$ with $Bx=\alpha$. Define a total coloring by

and, for edges,

Then modulo $3$,

Since $\alpha$ is proper, adjacent vertices have different residues modulo $3$, hence their integer full sums are unequal.

It remains to find such an $\alpha$.

If $G$ is non-bipartite and $G\ne K_4$, then by Brooks’ theorem $G$ has a proper $3$-coloring $\alpha:V(G)\to\mathbb F_3$. For a connected non-bipartite graph, $B$ has full row rank over $\mathbb F_3$: if $y^TB=0$, then $y_u+y_v=0$ for every edge $uv$; along an odd cycle this forces $y=0$. Thus $\operatorname{im}B=\mathbb F_3^{V(G)}$, so $\alpha\in\operatorname{im}B$.

If $G$ is bipartite with parts $A,B$, then $\operatorname{im}B$ consists exactly of vectors $\alpha$ satisfying

Because $|V(G)|\ge 3$, choose a proper such $\alpha$ as follows. If $|B|\ge2$, put $\alpha(a)=0$ for all $a\in A$, and choose values $\alpha(b)\in\{1,2\}$ with total sum $0$ modulo $3$. If $|B|=1$, put the unique vertex of $B$ in color $1$, and color two vertices of $A$ by $2$ and the rest by $0$, giving total $1$ modulo $3$. Hence again $\alpha\in\operatorname{im}B$.

Finally, for $G=K_4$, label vertices $0,1,2,3$ and define

The full sums are respectively

so all adjacent vertices are distinguished.

Thus every connected finite simple graph with $\Delta(G)=3$ admits a neighbor full sum distinguishing total $3$-coloring.

Citation: No prior complete resolution of this exact Problem 1 is used here. Definitions/problem: Chang, Yang, Yin, Yao, “An extension on neighbor sum distinguishing total coloring of graphs,” arXiv:2201.02781. Ingredient: Brooks’ theorem, R. L. Brooks, Proc. Cambridge Philos. Soc. 37 (1941), 194–197.