Acyclic edge colourings of graphs with large girth

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

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

Details

Original languageEnglish
Pages (from-to)511–533
JournalRandom Structures and Algorithms
Volume50
Issue number4
Early online date3 Nov 2016
Publication statusPublished - Jul 2017

Keywords

  • acyclic edge colorings, bounded degree graphs, semirandom method