Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-09T14:06:14.960Z Has data issue: false hasContentIssue false
  • English
  • Français

The Chromatic Number of Graph Powers

Published online by Cambridge University Press:  14 February 2002

NOGA ALON  and
BOJAN MOHAR
NOGA ALON
Affiliation:
Department of Mathematics, Tel Aviv University, Tel Aviv, Israel (e-mail: noga@math.tau.ac.il)
BOJAN MOHAR
Affiliation:
Department of Mathematics, University of Ljubljana, 1111 Ljubljana, Slovenia (e-mail: bohan.mohar@uni-lj.si)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 [ges ] 7. Extensions to higher powers are considered as well.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 1 , January 2002 , pp. 1 - 10
Copyright
2002 Cambridge University Press