ON CLOSED MODULAR COLORINGS OF TREES

NEW

Problem: Let $T$ be a finite simple tree of order $|V(T)|\ge 3$. For $k\ge2$, a closed modular $k$-coloring is a map

such that the induced closed-neighborhood sum

is a proper vertex-coloring: $c^*(u)\ne c^*(v)$ whenever $uv\in E(T)$. The conjecture is:

for every tree $T$ of order at least $3$.

Result: The conjecture is true.

Work in $F=\mathbb Z_3$. Root a tree at $r$. For a vertex $v$, let $\operatorname{ch}(v)$ be its children and set

For a rooted tree $R$ and an external parent color $p\in F$, call $c$ $p$-admissible if for every child $u$ of $v$,

where $p_r=p$ and $p_v=c(\operatorname{parent}(v))$ for $v\ne r$.

For the original rooted tree, $p=0$. Then for an edge $vu$ with $u$ a child of $v$,

so $c^*(v)\ne c^*(u)$ exactly when the admissibility inequality holds.

For a rooted tree $R$, define

We prove by induction that every rooted tree has one of the following five state-types:

A single vertex has type $L$.

Assume the root has child subtrees already classified. For fixed root color $x$, desired root child-sum $a$, and $q=a+p$, a child of type $L,E,A,B,C$ can contribute a child-root color $y$ respectively from:

This table follows directly from the edge condition $y+\sigma(\text{child})\ne q$.

Now classify the root.

If some child has type $E$, then $x=0$ is impossible, while for $x\ne0$ that child contributes freely, so the root has type $B$.

If no child has type $E$, but some child has type $A$ or $C$, then one child contributes freely for every $x,p,q$, so the root has type $A$.

It remains that all children have type $L$ or $B$. If there is exactly one $L$-child and no $B$-child, the root has type $E$. If there is exactly one $B$-child and no $L$-child, the root has type $C$. In every other case, the root has type $A$, because in $F=\mathbb Z_3$,

Thus the induction is complete.

Types $L$ and $E$ occur only for rooted trees of order $1$ and $2$. Hence any rooted tree of order at least $3$ has type $A$, $B$, or $C$, so $S_R(0)\ne\varnothing$. Choose a witnessing $0$-admissible coloring $c:V(T)\to\mathbb Z_3$. By the equivalence above, its closed-neighborhood sums form a proper coloring. Therefore $T$ has a closed modular $3$-coloring, and

The excluded order-$2$ case is genuinely degenerate: for $P_2$, the two vertices have identical closed neighborhoods, so their closed sums are always equal.

Citation: Definitions and conjecture: Bryan Phinezy and Ping Zhang, “On closed modular colorings of trees,” Discussiones Mathematicae Graph Theory 33 (2013), 411–428, doi:10.7151/dmgt.1678. The proof above is self-contained.