2014/12/22 by Ioannis Giotis, Lefteris M. Kirousis, Kostas I. Psaromiligkos +1 · 1 citation
Mathematics · Computer Science · Biochemistry, Genetics and Molecular Biology · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Genome Rearrangement Algorithms #Upper and lower bounds #Combinatorics #Edge coloring #Lemma (botany) #Mathematics #Discrete mathematics #Bounded function #Directed acyclic graph #Graph #Graph power #Line graph
paper · pdf · doi:10.1137/1.9781611973761.2
openalex publication_date 2014/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
The algorithm for Lovász Local Lemma by Moser and Tardos gives a constructive way to prove the existence of combinatorial objects that satisfy a system of constraints. We present an alternative probabilistic analysis of the algorithm that does not involve reconstructing the history of the algorithm from the witness tree. We apply our technique to improve the best known upper bound to acyclic chromatic index. Specifically we show that a graph with maximum degree Δ has an acyclic proper edge coloring with at most ⌈3.74(Δ − 1)⌉ +1 colors, whereas the previously known best bound was 4(Δ − 1). The same technique is also applied to improve corresponding bounds for graphs with bounded girth. An interesting aspect of this application is that the probability of the “undesirable” events do not have a uniform upper bound, i.e. it constitutes a case of the asymmetric Lovász Local Lemma.