COMPUTER SCIENCE COLLOQUIUM

AVD coloring and entropy compression.

William Lochet Department of Informatics University of Bergen, Norway

Tuesday, 04 December, 2018 at 14:15 IMADA's Seminar Room

ABSTRACT

A proper edge coloring of a graph is 'adjacent vertex distinguishing' (AVD) if no two adjacent vertices see the same set of colors. Using a clever application of the Local Lemma, Hatami (2006) proved that every graph with maximum degree D and no isolated edge has an AVD edge coloring with D + 300 colors, provided D is large enough. In this talk, I will outline a proof that D + 19 colors are enough, using entropy compression techniques.This is motivated by the conjecture that D + 2 colors are in fact enough. Joint work with Gwenael Joret.

Host: Jørgen Bang-Jensen

---

SDU HOME | IMADA HOME | Previous Page

---

Daniel Merkle