Acyclic edge colourings of graphs with large girth

DOI10.1002/RSA.20695MaRDI QIDQ4978429zbMATH OpenOpenAlexFDO

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

Publication date 10 August 2017

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.3047, http://pure-oai.bham.ac.uk/ws/files/29363271/Acyclic_coloring_with_large_girth.pdf

zbMATH Keywords

acyclic edge coloringsbounded degree graphssemirandom method

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

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 $varepsilon>0$, there exists a $g=g(varepsilon)$ such that if $G$ has girth at least $g$ then $G$ admits an acyclic edge colouring with at most $(1+varepsilon)Delta$ colours.

Recommendations

• Generalised acyclic edge colourings of graphs with large girth
• Acyclic edge coloring of graphs with large girths
• scientific article; zbMATH DE number 2140684
• Improved bounds on acyclic edge colouring
• Acyclic chromatic indices of planar graphs with large girth

Cites work

• A constructive proof of the general Lovász local lemma
• Acyclic coloring of graphs
• Acyclic colorings of planar graphs
• Acyclic edge colorings of graphs
• Acyclic edge-coloring using entropy compression
• An improvement of the Lovász local lemma via cluster expansion
• Asymptotically good list-colorings
• Improved bounds on acyclic edge colouring
• Improved bounds on coloring of graphs
• Models and thresholds for random constraint satisfaction problems
• Near-optimal list colorings
• New bounds for the acyclic chromatic index

Cited in

(12)

• List edge chromatic number of graphs with large girth
• Algorithmic aspects of acyclic edge colorings
• Generalized acyclic edge colorings via entropy compression
• Acyclic edge coloring of graphs with large girths
• A new bound on the acyclic edge chromatic number
• Improved bounds on acyclic edge colouring
• Edge-colorings of some large graphs on alphabets
• Acyclic coloring of graphs with some girth restriction
• New bounds for the acyclic chromatic index
• scientific article; zbMATH DE number 2140684 (Why is no real title available?)
• Acyclic and tree unique colourings in random graphs
• Generalised acyclic edge colourings of graphs with large girth

This page was built for publication: Acyclic edge colourings of graphs with large girth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978429)