# Chromatic number of square of a tree

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.

• Have you tried induction? It seems just removing a leaf should give you a matching upper bound.. – Joshua Erde Jul 1 at 21:48
• @JoshuaErde you mean the upper bound of $\Delta+1$ is right? – vidyarthi Jul 1 at 22:01

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$$.

• great! Is there any such result for bipartite graphs? – vidyarthi Jul 1 at 23:18
• The girth of the $k$-th power of a large cycle is large, and it particular it contains a large chordless cycle (so it is not chordal). – Louis Esperet Jul 2 at 8:42
• Moreover, the square of a 10-cycle contains chordless 5-cycles and hence is not perfect. – Timothy Chow Jul 2 at 23:22