Graph power

[4] For the special case of a square of a planar graph, Wegner conjectured in 1977 that the chromatic number of the square of a planar graph is at most max(Δ + 5, ⁠3Δ/2⁠ + 1), and it is known that the chromatic number is at most ⁠5Δ/3⁠ + O(1).

Although the chromatic number of the square of a nonplanar graph with maximum degree Δ may be proportional to Δ2 in the worst case, it is smaller for graphs of high girth, being bounded by O(Δ2 / log Δ) in this case.

[12] The kth power of a graph with n vertices and m edges may be computed in time O(mn) by performing a breadth first search starting from each vertex to determine the distances to all other vertices, or slightly faster using more sophisticated algorithms.

[13] Alternatively, If A is an adjacency matrix for the graph, modified to have nonzero entries on its main diagonal, then the nonzero entries of Ak give the adjacency matrix of the kth power of the graph,[14] from which it follows that constructing kth powers may be performed in an amount of time that is within a logarithmic factor of the time for matrix multiplication.

The kth powers of trees can be recognized in time linear in the size of the input graph.