You are cordially invited to our second Monday Lecture since
Corona crisis stopped our curriculum. You may find valid Invitation for zoom throughout all winter
term here: Invitation link: Second Monday Lecture will be on October 26th 2020 at 14:15 h.
Zoom - Invitation Time: Monday, October 26th - 14:15 h Lecture: Sophie Spirkl (University of Waterloo) Title: k-coloring graphs with forbidden induced subgraphs Abstract:A k-coloring of
a graph G is a function c that assigns an integer between 1 and
k to every vertex of G such that c(u) is not equal to c(v) for
every edge uv of G. Deciding, given a graph G, whether G has a
k-coloring, is NP-hard for all k at least 3.
In this talk, we will consider what happens when we restrict the input, that is: For a graph H and integer k, what is the complexity of deciding if a given graph G with no induced subgraph isomorphic to H has a k-coloring? We know the answer for many pairs H and k. Possibly the most interesting open cases are those in which H is a path; I will talk about recent results and open questions related to this. |