3
$\begingroup$

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.

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

1 Answer 1

Reset to default
7
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .