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.