Improved bounds on coloring of graphs
From MaRDI portal
Publication:412254
DOI10.1016/j.ejc.2011.12.002zbMath1244.05094arXiv1005.1875OpenAlexW2025737479MaRDI 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 (31)
New bounds for the acyclic chromatic index ⋮ Commutativity in the Algorithmic Lovász Local 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 1-planar graphs without 4-cycles ⋮ Hardness transitions and uniqueness of acyclic colouring ⋮ A new bound on the acyclic edge chromatic number ⋮ Further result on acyclic chromatic index of planar graphs ⋮ On \(r\)-acyclic edge colorings of planar graphs ⋮ Acyclic edge coloring of graphs ⋮ Acyclic edge coloring of 4-regular graphs without 3-cycles ⋮ The acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 4-cycle ⋮ Acyclic edge-coloring using entropy compression ⋮ Unnamed Item ⋮ 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\) ⋮ Generalized acyclic edge colorings via entropy compression ⋮ Linear arboricity of regular digraphs ⋮ Entropy compression versus Lovász local lemma ⋮ Acyclic edge coloring of 4-regular graphs. II. ⋮ On acyclic edge-coloring of complete bipartite graphs ⋮ Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles ⋮ Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Coloring graphs without bichromatic cycles or paths ⋮ Acyclic coloring of graphs and entropy compression method ⋮ Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas ⋮ Acyclic edge coloring of chordal graphs with bounded degree ⋮ Acyclic edge colourings of graphs with large girth ⋮ A Local Lemma for Focused Stochastic Algorithms ⋮ The local cut lemma
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
This page was built for publication: Improved bounds on coloring of graphs
