Την Παρασκευή 21 Οκτωβρίου στις 13:35, στην Αίθουσα Σεμιναρίων του τομέα Μαθηματικών (2ος όροφος, κτίριο Ε).
Title: “Choosability: a hard graph coloring problem”
Speaker: Valia Mitsou, Hungarian Academy of Sciences
Abstract: Choosability, independently introduced by Vizing in 1976 and by Erdős, Rubin, and Taylor in 1979 is a well-studied graph theoretic concept. We say that a graph G is k-choosable if for any assignment of lists of k colors on the verices of G we can to pick one color from each vertex’ list such that for every edge its endpoints receive different colors. We will present a number of graph theoretic and algorithmic results on the choosability problem and its generalization choosability deletion. This talk is based on recent work jointly done with Dr. Dániel Marx (“Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth”) which was presented at the conference ICALP 2016.