Acyclic edge colourings of graphs with large girth

Xing Shi Cai, Guillem Perarnau, Bruce H Reed, Adam Bene Watts

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
212 Downloads (Pure)


An edge colouring of a graph G is called acyclic if it is proper and every cycle contains at least three colours. We show that for every inline image, there exists a inline image such that if G has maximum degree Δ and girth at least g then G admits an acyclic edge colouring with inline image colours. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016
Original languageEnglish
Pages (from-to)511–533
JournalRandom Structures and Algorithms
Issue number4
Early online date3 Nov 2016
Publication statusPublished - Jul 2017


  • acyclic edge colorings
  • bounded degree graphs
  • semirandom method


Dive into the research topics of 'Acyclic edge colourings of graphs with large girth'. Together they form a unique fingerprint.

Cite this