Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952251 | Theoretical Computer Science | 2017 | 11 Pages |
Abstract
We give a probabilistic analysis of a Moser-type algorithm for the Lová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 Î has an acyclic proper edge coloring with at most â3.74(Îâ1)â+1 colors, whereas, previously, the best bound was 4(Îâ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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos,