Combinatorics, Probability & Computing



The Chromatic Number of Graph Powers


NOGA ALON a1 1 and BOJAN MOHAR a2 2
a1 Department of Mathematics, Tel Aviv University, Tel Aviv, Israel (e-mail: noga@math.tau.ac.il)
a2 Department of Mathematics, University of Ljubljana, 1111 Ljubljana, Slovenia (e-mail: bohan.mohar@uni-lj.si)

Abstract

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)



Footnotes

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.