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.

  • $\begingroup$ Have you tried induction? It seems just removing a leaf should give you a matching upper bound.. $\endgroup$ – Joshua Erde Jul 1 at 21:48
  • $\begingroup$ @JoshuaErde you mean the upper bound of $\Delta+1$ is right? $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ great! Is there any such result for bipartite graphs? $\endgroup$ – vidyarthi Jul 1 at 23:18
  • 1
    $\begingroup$ 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). $\endgroup$ – Louis Esperet Jul 2 at 8:42
  • 1
    $\begingroup$ Moreover, the square of a 10-cycle contains chordless 5-cycles and hence is not perfect. $\endgroup$ – Timothy Chow Jul 2 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.