Acyclic edge coloring through the Lovász Local Lemma

Ioannis Giotis; Lefteris Kirousis; Kostas I. Psaromiligkos; Dimitrios M. Thilikos

doi:10.1016/j.tcs.2016.12.011

Acyclic edge coloring through the Lovász Local Lemma

Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	40-50
Number of pages	11
Journal	Theoretical Computer Science
Volume	665
DOIs	https://doi.org/10.1016/j.tcs.2016.12.011
State	Published - Feb 22 2017

Keywords

Acyclic edge coloring
Algorithmic proof of the Lovász Local Lemma

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2016.12.011

Cite this

@article{8a8a56833d9a4fca8d7131a826957b27,

title = "Acyclic edge coloring through the Lov{\'a}sz Local Lemma",

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 Δ 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 = "Acyclic edge coloring, Algorithmic proof of the Lov{\'a}sz Local Lemma",

author = "Ioannis Giotis and Lefteris Kirousis and Psaromiligkos, {Kostas I.} and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier B.V.",

year = "2017",

month = feb,

day = "22",

doi = "10.1016/j.tcs.2016.12.011",

language = "English (US)",

volume = "665",

pages = "40--50",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Acyclic edge coloring through the Lovász Local Lemma

AU - Giotis, Ioannis

AU - Kirousis, Lefteris

AU - Psaromiligkos, Kostas I.

AU - Thilikos, Dimitrios M.

PY - 2017/2/22

Y1 - 2017/2/22

N2 - 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.

AB - 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.

KW - Acyclic edge coloring

KW - Algorithmic proof of the Lovász Local Lemma

UR - http://www.scopus.com/inward/record.url?scp=85008500306&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85008500306&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2016.12.011

DO - 10.1016/j.tcs.2016.12.011

M3 - Article

AN - SCOPUS:85008500306

SN - 0304-3975

VL - 665

SP - 40

EP - 50

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Acyclic edge coloring through the Lovász Local Lemma

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this