Improved bounds on coloring of graphs
From MaRDI portal
Publication:412254
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
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