The Chromatic Number of Graph Powers
It is shown that the maximum possible chromatic number of the square of a graph with maximum degree d and girth g is (1 +o(1))d2 if g = 3, 4, 5 or 6, and is Θ(d2 / log d) if g [gt-or-equal, slanted] 7. Extensions to higher powers are considered as well.(Received September 4 2000)
(Revised June 28 2001)
1 Research supported in part by a USA–Israel BSF grant and by a grant from the Israel Science Foundation.
2 Supported in part by the Ministry of Science and Technology of Slovenia, Research Project J1–0502–0101–98.