Acyclic edge-coloring using entropy compression
From MaRDI portal
Publication:2444732
Abstract: An edge-coloring of a graph G is acyclic if it is a proper edge-coloring of G and every cycle contains at least three colors. We prove 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). Our bound results from the analysis of a very simple randomised procedure using the so-called entropy compression method. We show that the expected running time of the procedure is O(mn Delta^2 log Delta), where n and m are the number of vertices and edges of G. Such a randomised procedure running in expected polynomial time was only known to exist in the case where at least 16 Delta colors were available. Our aim here is to make a pedagogic tutorial on how to use these ideas to analyse a broad range of graph coloring problems. As an application, also show that every graph with maximum degree Delta has a star coloring with 2 sqrt(2) Delta^{3/2} + Delta colors.
Recommendations
- Generalized acyclic edge colorings via entropy compression
- Acyclic coloring of graphs and entropy compression method
- Nonrepetitive colouring via entropy compression
- Algorithmic aspects of acyclic edge colorings
- Acyclic edge coloring of sparse graphs
- Acyclic edge coloring of graphs
- Acyclic edge colorings of graphs
- Acyclic edge-colorings of sparse graphs
- Efficient algorithms for acyclic colorings of graphs
- Optimal acyclic edge colouring of grid like graphs
Cites work
- A constructive proof of the general Lovász local lemma
- A constructive proof of the Lovász local lemma
- Acyclic coloring of graphs
- Acyclic edge colorings of graphs
- An improvement of the Lovász local lemma via cluster expansion
- Analytic combinatorics
- scientific article; zbMATH DE number 3603300 (Why is no real title available?)
- scientific article; zbMATH DE number 1775440 (Why is no real title available?)
- scientific article; zbMATH DE number 2232270 (Why is no real title available?)
- Improved bounds on acyclic edge colouring
- Improved bounds on coloring of graphs
- New approach to nonrepetitive sequences
- New constructive aspects of the Lovász local lemma
- Nonrepetitive colouring via entropy compression
- Star coloring of graphs
- The complexity of nonrepetitive coloring
Cited in
(52)- The list chromatic number of graphs with small clique number
- Acyclic edge coloring of 4-regular graphs without 3-cycles
- Generalized arboricity of graphs with large girth
- Generalized acyclic edge colorings via entropy compression
- An upper bound for the choice number of star edge coloring of graphs
- Entropy compression versus Lovász local lemma
- Coloring graphs without bichromatic cycles or paths
- Acyclic edge coloring of chordal graphs with bounded degree
- Local conditions for planar graphs of acyclic edge coloring
- Another approach to non-repetitive colorings of graphs of bounded degree
- A new bound on the acyclic edge chromatic number
- Acyclic edge coloring of 4-regular graphs. II.
- Acyclic coloring of graphs and entropy compression method
- Counting Gallai 3-colorings of complete graphs
- The local cut lemma
- Acyclic chromatic index of triangle-free 1-planar graphs
- Improved upper bound for the degenerate and star chromatic numbers of graphs
- Acyclic edge coloring of graphs
- The acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 4-cycle
- (2+ )-nonrepetitive list colouring of paths
- Moser-Tardos resampling algorithm, entropy compression method and the subset gas
- New bounds for the acyclic chromatic index
- Application of entropy compression in pattern avoidance
- Acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 6-cycle
- An algorithmic proof of the Lovász local lemma via resampling oracles
- Acyclic edge colourings of graphs with large girth
- Acyclic list edge coloring of graphs with maximum degree 4
- Acyclic edge coloring through the Lovász local lemma
- A general framework for hypergraph coloring
- Progress on the adjacent vertex distinguishing edge coloring conjecture
- Nonrepetitive colouring via entropy compression
- A local lemma for focused stochastic algorithms
- Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles
- Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles
- Counting colorings of triangle-free graphs
- Acyclic edge coloring of 1-planar graphs without 4-cycles
- Edge colorings avoiding patterns
- On triangle-free list assignments
- Planar graphs are acyclically edge \((\Delta + 5)\)-colorable
- Coloring of graphs avoiding bicolored paths of a fixed length
- On harmonious coloring of hypergraphs
- Edge colorings avoiding patterns
- Proper conflict-free coloring of graphs with large maximum degree
- Acyclically edge color triangle-free toroidal graphs in + 2 colors
- Acyclic chromatic index of IC-planar graphs
- Acyclic colorings of graphs with obstructions
- A linear-time algorithm for (1+)-edge-coloring
- On acyclic edge-coloring of complete bipartite graphs
- Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
- Analysis of a heuristic for acyclic edge colouring
- Acyclic coloring of graphs without bichromatic long path
- Further result on acyclic chromatic index of planar graphs
This page was built for publication: Acyclic edge-coloring using entropy compression
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2444732)
