# New bounds for the acyclic chromatic index

@article{Bernshteyn2016NewBF, title={New bounds for the acyclic chromatic index}, author={Anton Bernshteyn}, journal={Discret. Math.}, year={2016}, volume={339}, pages={2543-2552} }

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 ' ( G ) . Fiamcik (1978) and independently Alon, Sudakov, and Zaks (2001) conjectured that a ' ( G ) ź Δ ( G ) + 2 , where Δ ( G ) denotes the maximum degree of G . The best known general bound is a ' ( G ) ź 4… Expand

#### Figures and Topics from this paper

#### 9 Citations

Acyclic edge colourings of graphs with large girth

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2017

An edge colouring of a graph G is called acyclic if it is proper and every cycle contains at least three colours and there exists a $g=g(\varepsilon)$ such that if G has girth at least $g$ then $G$ admits an acyClic edge colourings with at most $(1+\varpsilon)\Delta$ colours. Expand

Generalized acyclic edge colorings via entropy compression

- Physics, Computer Science
- J. Comb. Optim.
- 2018

It is proved in this paper that for every graph G with girth at least two r-acyclic edge chromatic number at least 2r-1, A'_r( G) = 9r-7Δ+10r-12 holds and the approach is based on the entropy compression method. Expand

A new bound on the acyclic edge chromatic number

- Computer Science, Mathematics
- Discret. Math.
- 2020

A new bound is obtained for the acyclic edge chromatic number of a graph G with maximum degree Δ proving that a ′ ( G ) ≤ 3 . Expand

The Local Cut Lemma

- Mathematics, Computer Science
- Eur. J. Comb.
- 2017

This paper provides a generalization of the LLL which implies a random cut in a directed graph with certain properties, and presents an improved lower bound on the number of edges in color-critical hypergraphs. Expand

A New Perspective on Stochastic Local Search and the Lovasz Local Lemma

- Computer Science, Mathematics
- ArXiv
- 2018

We present a new perspective on the analysis of stochastic local search algorithms via linear algebra. Our key insight is that LLL-inspired convergence arguments can be seen as a method for bounding… Expand

Backtracking and Commutative Algorithms for the LLL

- Computer Science
- 2017

This work extends the framework of Achlioptas and Iliopoulos~\cite{AI} and provides a Local Lemma criterion that can capture every application of backtracking algorithms the authors are aware of and more and shows that for commutative algorithms, the witness tree lemma holds. Expand

Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications

- Computer Science, Mathematics
- 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
- 2019

A new convergence condition is introduced that seamlessly handles resampling, backtracking, and hybrid algorithms, i.e., algorithms that perform both resamplings and backtracking steps, and allows for the analysis of hybrid algorithms which were outside the scope of previous techniques. Expand

Focused Stochastic Local Search and the Lovász Local Lemma

- Computer Science, Mathematics
- SODA
- 2016

We develop tools for analyzing focused stochastic local search algorithms. These are algorithms which search a state space probabilistically by repeatedly selecting a constraint that is violated in… Expand

#### References

SHOWING 1-10 OF 15 REFERENCES

Acyclic edge colorings of graphs

- Mathematics
- 2001

A proper coloring of the edges of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an… Expand

Acyclic Coloring of Graphs

- Mathematics, Computer Science
- Random Struct. Algorithms
- 1991

It is shown that if G has maximum degree d, then A(G) = 0(d4/3) as d → ∞, which settles a problem of Erdos who conjectured, in 1976, that A( G) = o(d2) as d →∞. Expand

Acyclic edge-coloring using entropy compression

- Computer Science, Mathematics
- Eur. J. Comb.
- 2013

It is proved that every graph with maximum degree Delta has an acyclic edge-coloring with at most 4 Delta - 4 colors, improving the previous bound of 9.62 (Delta - 1). Expand

Improved bounds on coloring of graphs

- Computer Science, Mathematics
- Eur. J. Comb.
- 2012

Given a graph G with maximum degree @D>=3, we prove that the acyclic edge chromatic number a^'(G) of G is such that a^'(G)@[email protected]?9.62(@D-1)@?. Moreover we prove that: a^'(G)@[email… Expand

Asymptotics of the list-chromatic index for multigraphs

- Computer Science
- Random Struct. Algorithms
- 2000

The list-chromatic index, χ′ l (G) of a multigraph G, is the least t such that if S(A) is a set of size t for each A ∈ E := E(G), then there exists a proper coloring σ of G with σ(A), which is at least the fractional chromatic index. Expand

Acyclic colorings of planar graphs

- Mathematics
- 1973

A coloring of the vertices of a graph byk colors is called acyclic provided that no circuit is bichromatic. We prove that every planar graph has an acyclic coloring with nine colors, and conjecture… Expand

Acyclic edge colourings of graphs with large girth

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2017

An edge colouring of a graph G is called acyclic if it is proper and every cycle contains at least three colours and there exists a $g=g(\varepsilon)$ such that if G has girth at least $g$ then $G$ admits an acyClic edge colourings with at most $(1+\varpsilon)\Delta$ colours. Expand

The Local Cut Lemma

- Mathematics, Computer Science
- Eur. J. Comb.
- 2017

This paper provides a generalization of the LLL which implies a random cut in a directed graph with certain properties, and presents an improved lower bound on the number of edges in color-critical hypergraphs. Expand

The Local Action Lemma

- Mathematics
- 2014

The Lov\'{a}sz Local Lemma is a very powerful tool in probabilistic combinatorics, that is often used to prove existence of combinatorial objects satisfying certain constraints. Moser and Tardos have… Expand

A constructive proof of the general lovász local lemma

- Computer Science, Mathematics
- JACM
- 2010

This article improves upon recent findings so as to provide a method for making almost all known applications of the general Local Lemma algorithmic. Expand