Lecture by Sophie Spirkl (University of Waterloo): k-coloring graphs with forbidden induced subgraphs
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.
Time & Location
Oct 26, 2020 | 02:15 PM