New bounds for the acyclic chromatic index

DOI10.1016/J.DISC.2016.05.002zbMATH Open1339.05110arXiv1412.6237OpenAlexW1758674513MaRDI QIDQ294561FDOQ294561

Authors: Anton Bernshteyn 

Publication date: 16 June 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

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$.

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

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

zbMATH Keywords

acyclic edge coloringlocal cut lemmaLovász local lemma

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Acyclic colorings of planar graphs
• Improved bounds on acyclic edge colouring
• Acyclic edge colorings of graphs
• Acyclic coloring of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a problem of K. Zarankiewicz
• The local cut lemma
• Acyclic edge-coloring using entropy compression
• An improvement of the Lovász local lemma via cluster expansion
• A constructive proof of the general Lovász local lemma
• Improved bounds on coloring of graphs
• Title not available (Why is that?)
• Acyclic edge colourings of graphs with large girth

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
• On harmonious coloring of hypergraphs
• Improved bounds on coloring of graphs
• 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)