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](https://en.wikipedia.org/wiki/Graph_power) 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.



Chromatic number of square of a tree
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](https://en.wikipedia.org/wiki/Strongly_chordal_graph) 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$.


