Acyclic edge coloring through the Lovász local lemma

DOI10.1016/J.TCS.2016.12.011zbMATH Open1357.05042arXiv1407.5374OpenAlexW2962835057WikidataQ124839505 ScholiaQ124839505MaRDI QIDQ507595FDOQ507595

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)

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.

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

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

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)

Cites Work

• NIST digital library of mathematical functions
• NIST handbook of mathematical functions
• Analytic combinatorics
• Acyclic edge colorings of graphs
• Title not available (Why is that?)
• Acyclic edge-coloring using entropy compression
• A constructive proof of the general Lovász local lemma
• Title not available (Why is that?)
• A constructive proof of the Lovász local lemma
• On the algorithmic Lovász local lemma and acyclic edge coloring

Cited In (19)

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

Uses Software

• Digital Library of Mathematical Functions
• 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)