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)
152 Downloads (Pure)

Abstract

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
Volume50
Issue number4
Early online date3 Nov 2016
DOIs
Publication statusPublished - Jul 2017

Keywords

  • acyclic edge colorings
  • bounded degree graphs
  • semirandom method

Fingerprint

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

Cite this