Acyclic edge coloring through the Lovász local lemma

DOI10.1016/J.TCS.2016.12.011MaRDI QIDQ507595zbMATH OpenOpenAlexWikidataFDO

Authors Ioannis Giotis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos, L. M. Kirousis

Publication date 6 February 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

acyclic edge coloringalgorithmic proof of the Lovász local lemma

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

Abstract: We give a probabilistic analysis of a Moser-type algorithm for the Lov'{a}sz Local Lemma (LLL), adjusted to search for acyclic edge colorings of a graph. We thus improve the best known upper bound to acyclic chromatic index, also obtained by analyzing a similar algorithm, but through the entropic method (basically counting argument). Specifically we show that a graph with maximum degree $Delta$ has an acyclic proper edge coloring with at most $lceil3.74(Delta-1)ceil+1$ colors, whereas, previously, the best bound was $4(Delta-1)$. The main contribution of this work is that it comprises a probabilistic analysis of a Moser-type algorithm applied to events pertaining to dependent variables.

Recommendations

• On the algorithmic Lovász local lemma and acyclic edge coloring
• Acyclic colorings of locally planar graphs
• Local conditions for planar graphs of acyclic edge coloring
• Acyclic edge colorings of graphs
• Acyclic edge coloring of graphs
• Hypergraph colouring and the Lovász local lemma
• Coloring and the Lovász local lemma
• Distributed edge coloring and a special case of the constructive Lovász local lemma
• Acyclicity in edge-colored graphs
• Acyclic edge-coloring of planar graphs

Cites work

• scientific article; zbMATH DE number 3603300 (Why is no real title available?)
• scientific article; zbMATH DE number 3273761 (Why is no real title available?)
• A constructive proof of the Lovász local lemma
• A constructive proof of the general Lovász local lemma
• Acyclic edge colorings of graphs
• Acyclic edge-coloring using entropy compression
• Analytic combinatorics
• NIST digital library of mathematical functions
• NIST handbook of mathematical functions
• On the algorithmic Lovász local lemma and acyclic edge coloring

Cited in

(19)

• On the algorithmic Lovász local lemma and acyclic edge coloring
• Acyclic list edge coloring of graphs with maximum degree 4
• Acyclic coloring of graphs and entropy compression method
• Acyclic edge coloring of chordal graphs with bounded degree
• Entropy compression versus Lovász local lemma
• Combinatorial constructions of separating codes
• Planar graphs are acyclically edge \((\Delta + 5)\)-colorable
• Commutativity in the Algorithmic Lovász Local Lemma
• Acyclic chromatic index of chordless graphs
• On acyclic edge-coloring of complete bipartite graphs
• Acyclic edge coloring of 1-planar graphs without 4-cycles
• A new bound on the acyclic edge chromatic number
• A local lemma for focused stochastic algorithms
• Acyclic chromatic index of triangle-free 1-planar graphs
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles
• Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles
• Further result on acyclic chromatic index of planar graphs
• An algorithmic proof of the Lovász local lemma via resampling oracles

Describes a project that uses

Uses Software

• DLMF
• Maple

This page was built for publication: Acyclic edge coloring through the Lovász local lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507595)