BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: A k-coloring of a graph G is a function c that assigns an inte
ger 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-co
loring\, 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 integ
er k\, what is the complexity of deciding if a given graph G with no induce
d 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 t
o this.
DTSTAMP:20201007T215600
DTSTART:20201026T141500
CLASS:PUBLIC
LOCATION:online\n
SEQUENCE:0
SUMMARY:Sophie Spirkl (University of Waterloo): k-coloring graphs with forb
idden induced subgraphs
UID:107734746@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20201026-L-Sophie-Spirkl.html
END:VEVENT
END:VCALENDAR