Acyclic edge coloring through the Lovász Local Lemma

详细信息    查看全文

• 作者：Ioannis Giotis^a ; ^c ; ^{igiotis@cs.upc.edu} ; Lefteris Kirousis^a ; ^c ; ^{lkirousis@math.uoa.gr} ; Kostas I. Psaromiligkos^a ; ^{kostaspsa@gmail.com} ; Dimitrios M. Thilikos^a ; ^b ; ^c ; ^{sedthilk@thilikos.info}
• 关键词：Acyclic edge coloring ; Algorithmic proof of the Lová ; sz Local Lemma
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：22 February 2017
• 年：2017
• 卷：665
• 期：Complete
• 页码：40-50
• 全文大小：357 K
• 卷排序：665

文摘

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⌈3.74(Δ−1)⌉+1 colors, whereas, previously, the best bound was 4(Δ−1)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.