Acyclic edge colourings of graphs with large girth. Issue 4 (3rd November 2016)

• Record Type: Journal Article
• Authors: Cai, X. S.; Perarnau, G.; Reed, B.; Watts, A. B.
• Is Part Of: Random structures & algorithms. Volume 50:Issue 4(2017)
• Page Start: 511
• Page End: 533
• Publication Date: 2016-11-03
• Subjects: acyclic edge colorings -- bounded degree graphs -- semirandom method; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20695
• Languages: English
• ISSNs: 1042-9832

Abstract

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 ε > 0, there exists a g = g ( ε ) such that if G has maximum degree Δ and girth at least g then G admits an acyclic edge colouring with ( 1 + ε ) Δ + O ( 1 ) colours. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 511–533, 2017