New bounds for the acyclic chromatic index

DOI10.1016/J.DISC.2016.05.002MaRDI QIDQ294561zbMATH OpenOpenAlexFDO

Authors Anton Bernshteyn

Publication date 16 June 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.6237

zbMATH Keywords

acyclic edge coloringlocal cut lemmaLovász local lemma

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: An edge coloring of a graph $G$ is called an acyclic edge coloring if it is proper and every cycle in $G$ contains edges of at least three different colors. The least number of colors needed for an acyclic edge coloring of $G$ is called the acyclic chromatic index of $G$ and is denoted by $a^{\prime }(G)$. Fiamv{c}ik and independently Alon, Sudakov, and Zaks conjectured that $a^{\prime }(G)leqDelta(G)+2$, where $Delta(G)$ denotes the maximum degree of $G$. The best known general bound is $a^{\prime }(G)leq4(Delta(G)-1)$ due to Esperet and Parreau. We apply a generalization of the Lov'{a}sz Local Lemma to show that if $G$ contains no copy of a given bipartite graph $H$, then $a^{\prime }(G)leq3Delta(G)+o(Delta(G))$. Moreover, for every $varepsilon>0$, there exists a constant $c$ such that if $g(G)geqc$, then $a^{\prime }(G)leq(2+varepsilon)Delta(G)+o(Delta(G))$, where $g(G)$ denotes the girth of $G$.

Recommendations

• Improved upper bounds on acyclic edge colorings
• Improved bounds on acyclic edge colouring
• A new upper bound on the acyclic chromatic indices of planar graphs
• Improved bounds on the generalized acyclic chromatic number
• Improved bounds on coloring of graphs

Cites work

• scientific article; zbMATH DE number 3603300 (Why is no real title available?)
• scientific article; zbMATH DE number 1523257 (Why is no real title available?)
• scientific article; zbMATH DE number 1775440 (Why is no real title available?)
• 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 colourings of graphs with large girth
• Acyclic edge-coloring using entropy compression
• An improvement of the Lovász local lemma via cluster expansion
• Improved bounds on acyclic edge colouring
• Improved bounds on coloring of graphs
• On a problem of K. Zarankiewicz
• The local cut lemma

Cited in

(13)

• A new method of proving theorems on chromatic index
• Generalized acyclic edge colorings via entropy compression
• New Bounds of Induced Acyclic Graphoidal Decomposition Number of a Graph
• Acyclic edge colourings of graphs with large girth
• Improved bounds on coloring of graphs
• On harmonious coloring of hypergraphs
• On acyclic edge-coloring of complete bipartite graphs
• A new bound on the acyclic edge chromatic number
• New results on chromatic index critical graphs
• Upper bounds on the acyclic chromatic index of degenerate graphs
• Improved bounds on acyclic edge colouring
• A new upper bound on the acyclic chromatic indices of planar graphs
• The local cut lemma

This page was built for publication: New bounds for the acyclic chromatic index

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