[Facets-of-complexity] Invitation to Monday Lecture - October 26th 2020 - online via zoom

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our second Monday Lecture since Corona crisis stopped our curriculum.
All Monday Lectures and Colloquia of winter term 20/21 will be held online via zoom.

You may find valid Invitation for zoom throughout all winter term here:
http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Second Monday Lecture will be on October 26th 2020 at 14:15 h.

Online via:
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.