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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics