×

On closed modular colorings of trees. (English) Zbl 1333.05078

Let \(c: V(G)\to \mathbb{Z}_k\) be a colouring of the vertices of \(G\). Adjacent vertices can be assigned the same colour. This colouring indices a colouring \(c^\prime:V(G)\to \mathbb{Z}_k\) defined by \(c^\prime(v)=\sum\deg(u)\), where the sum is taken over all \(u\) in the closed neighbourhood of \(v\). Then \(c\) is called a closed modular \(k\)-colouring of \(G\) if \(c^\prime(v)\not=c^\prime(w)\) whenever \(v\) and \(w\) are adjacent except when both have the same closed neighbourhood. The closed modular chromatic number \(\overline{mc}(G)\) of \(G\) is the minimum \(k\) for which \(G\) has a closed modular \(k\)-colouring.
This parameter is studied for certain classes of trees such as caterpillars, and it is shown that, for the trees \(T\) considered, \(\overline{mc}(T)\) is equal to 2 or 3. It is also shown that every tree \(T\) of order at least 4 has a closed modular 4-colouring \(c\) such that \(c(v)\not=0\) for all \(v\) in \(T\).

MSC:

05C05 Trees
05C15 Coloring of graphs and hypergraphs