Acyclic edge colourings of graphs with large girth

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

doi:10.1002/rsa.20695

Acyclic edge colourings of graphs with large girth

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

Mathematics

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

226 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 language	English
Pages (from-to)	511–533
Journal	Random Structures and Algorithms
Volume	50
Issue number	4
Early online date	3 Nov 2016
DOIs	https://doi.org/10.1002/rsa.20695
Publication status	Published - Jul 2017

Keywords

acyclic edge colorings
bounded degree graphs
semirandom method

Access to Document

10.1002/rsa.20695

Acyclic coloring with large girth
This is the peer reviewed version of the following article: Cai, X. S., Perarnau, G., Reed, B. and Watts, A. B. (2016), Acyclic edge colourings of graphs with large girth. Random Struct. Alg., which has been published in final form at: http://dx.doi.org/10.1002/rsa.20695. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving Checked for eligibility:14/07/2016
Accepted author manuscript, 337 KBLicence: None: All rights reserved

Cite this

@article{2e3f012cf66844bfb65f48cd7c4f835a,

title = "Acyclic edge colourings of graphs with large girth",

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. {\textcopyright} 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016",

keywords = "acyclic edge colorings, bounded degree graphs, semirandom method",

author = "Cai, {Xing Shi} and Guillem Perarnau and Reed, {Bruce H} and Watts, {Adam Bene}",

year = "2017",

month = jul,

doi = "10.1002/rsa.20695",

language = "English",

volume = "50",

pages = "511–533",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "Wiley",

number = "4",

}

TY - JOUR

T1 - Acyclic edge colourings of graphs with large girth

AU - Cai, Xing Shi

AU - Perarnau, Guillem

AU - Reed, Bruce H

AU - Watts, Adam Bene

PY - 2017/7

Y1 - 2017/7

N2 - 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

AB - 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

KW - acyclic edge colorings

KW - bounded degree graphs

KW - semirandom method

U2 - 10.1002/rsa.20695

DO - 10.1002/rsa.20695

M3 - Article

SN - 1042-9832

VL - 50

SP - 511

EP - 533

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 4

ER -

Acyclic edge colourings of graphs with large girth

Abstract

Keywords

Access to Document

Fingerprint

Cite this