### 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))d^{2} if g = 3, 4, 5 or 6, and is Θ(d^{2}/log d) if g ≥ 7. Extensions to higher powers are considered as well.

Original language | English (US) |
---|---|

Pages (from-to) | 1-10 |

Number of pages | 10 |

Journal | Combinatorics Probability and Computing |

Volume | 11 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2002 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

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

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

## Cite this

Alon, N., & Mohar, B. (2002). The chromatic number of graph powers.

*Combinatorics Probability and Computing*,*11*(1), 1-10. https://doi.org/10.1017/S0963548301004965