The chromatic number of graph powers

Noga Alon, Bojan Mohar

Research output: Contribution to journalArticlepeer-review

42 Scopus citations


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

Original languageEnglish (US)
Pages (from-to)1-10
Number of pages10
JournalCombinatorics Probability and Computing
Issue number1
StatePublished - Jan 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'The chromatic number of graph powers'. Together they form a unique fingerprint.

Cite this