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, Acyclic edge colourings of graphs with large girth, 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, 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