Improved bounds on coloring of graphs

DOI10.1016/j.ejc.2011.12.002zbMath1244.05094arXiv1005.1875MaRDI QIDQ412254

Aldo Procacci, Benedetto Scoppola, Sokol Ndreca

Publication date: 4 May 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

acyclic edge chromatic number

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C07: Vertex degrees

Related Items

Commutativity in the Algorithmic Lovász Local Lemma, Unnamed Item, An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles, Acyclic edge colourings of graphs with large girth, 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, Acyclic edge coloring of 1-planar graphs without 4-cycles, Hardness transitions and uniqueness of acyclic colouring, New bounds for the acyclic chromatic index, On \(r\)-acyclic edge colorings of planar graphs, Acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 6-cycle, On acyclic edge-coloring of the complete bipartite graphs \(K_{2p-1, 2p-1}\) for odd prime \(p\), 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, Further result on acyclic chromatic index of planar graphs, Acyclic edge coloring of 4-regular graphs without 3-cycles, Generalized acyclic edge colorings via entropy compression, Linear arboricity of regular digraphs, Entropy compression versus Lovász local lemma, Coloring graphs without bichromatic cycles or paths, Acyclic edge coloring of chordal graphs with 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, 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, Acyclic edge-coloring using entropy compression

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on acyclic edge coloring of complete bipartite graphs
• On a problem of Spencer
• Colouring a graph frugally
• Cluster expansion for abstract polymer models. New bounds from an old approach
• Improved bounds on acyclic edge colouring
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions
• Acyclic edge colorings of graphs
• Properly coloured copies and rainbow copies of large graphs with small maximum degree
• An Improvement of the Lovász Local Lemma via Cluster Expansion
• Star coloring of graphs
• Regions Without Complex Zeros for Chromatic Polynomials on Graphs with Bounded Degree
• A constructive proof of the general lovász local lemma
• Acyclic edge coloring of graphs with maximum degree 4
• Acyclic coloring of graphs
• Acyclic Edge Colouring of Outerplanar Graphs