A new bound on the acyclic edge chromatic number

DOI10.1016/J.DISC.2020.112037MaRDI QIDQ2198378zbMATH OpenOpenAlexFDO

Authors Paula Mendes Soares Fialho, Aldo Procacci, Bernardo Nunes Borges de Lima

Publication date 10 September 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2020.112037

zbMATH Keywords

randomized algorithmsprobabilistic method in combinatoricsLovász local lemma

Mathematics Subject Classification ID

Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15)

Recommendations

• A note on acyclic vertex-colorings
• Improved upper bounds on acyclic edge colorings
• Improved bounds on acyclic edge colouring
• New bounds for the acyclic chromatic index
• Improved bounds on the generalized acyclic chromatic number

Cites work

• scientific article; zbMATH DE number 3603300 (Why is no real title available?)
• scientific article; zbMATH DE number 1775440 (Why is no real title available?)
• A constructive proof of the Lovász local lemma
• A constructive proof of the general Lovász local lemma
• Acyclic coloring of graphs
• Acyclic edge coloring through the Lovász local lemma
• Acyclic edge colorings of graphs
• Acyclic edge colourings of graphs with large girth
• Acyclic edge-coloring using entropy compression
• An improvement of the Lovász local lemma via cluster expansion
• Analytic combinatorics
• Improved bounds on coloring of graphs
• New bounds for the acyclic chromatic index
• Nonrepetitive colouring via entropy compression
• On the facial Thue choice index via entropy compression

Cited in

(7)

• Improved upper bounds on acyclic edge colorings
• Entropy compression versus Lovász local lemma
• Upper bounds on the acyclic chromatic index of degenerate graphs
• A note on acyclic vertex-colorings
• Bounds on the generalised acyclic chromatic numbers of bounded degree graphs
• A new upper bound on the acyclic chromatic indices of planar graphs
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas

This page was built for publication: A new bound on the acyclic edge chromatic number

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