Chromatic number of square of a tree

Question

What is an upper bound on the chromatic number of the square of a tree on $n$ vertices? Note that the power of the graph is considered in this sense.

If the tree were a path, then it is easy to see that the chromatic number is $3$ if the order is a multiple of $3$. This is because a path of order a multiple of $3$ has a triangle, therefore should require at least $3$ colors. Next, the square of a cycle on $n$ vertices where $n$ is divisible by $3$, has chromatic number $3$. In other cases, I think it equals $\Delta+1$, where $\Delta$ be the maximum degree of the tree. This is because, each star of order $\Delta$ in the tree induces a clique of order $\Delta+1$ in the square graph. But, can it be more than $\Delta+1$. Specifically, the maximum degree of the square graph is $2\Delta$ where $\Delta $ be the maximum degree of the tree. Any hints? Thanks beforehand.

Answer 1

The particular case of the square of a tree is easy to handle by producing a greedy $(\Delta+1)$-coloring starting from a root vertex and extending. However, much stronger results are known:

The $k$-th power of a tree was shown to be chordal in

Y.-L. Lin, S. Skiena, "Algorithms for Square Roots of Graphs", SIAM Journal of Discrete Mathematics, 8(1), 99-118, 1995

and even strongly chordal in

D. G. Corneil, P. E. Kearney, "Tree Powers", Journal of Algorithms, 29,111-131, 1998

Chordal graphs are perfect, so their chormatic number is the same as the size of the largest clique. The largest clique in the k-th power of a tree $T$ is the largest $k$-ball in $T$, where a $k$-ball centered at a vertex $v$ is the set of all vertices of $T$ which are at a distance $\le k$ from $v$.