BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION:  For several graph classes without long induced paths there ex
 ists a finite forbidden subgraph characterization for k-colourability. Such
  a finite set of minimal obstructions allows to provide a “no-certificate" 
 which proves that a graph is not k-colourable.      We prove that there are
  only finitely many 4-critical P 6 -free graphs\, and give the complete lis
 t that consists of 24 graphs. In particular\, we obtain a certifying algori
 thm for 3-colouring P 6 -free graphs\, which solves an open problem posed b
 y Golovach et al. (Here\, P 6  denotes the induced path on six vertices.)  
      Our result leads to the following dichotomy theorem: if H is a connect
 ed graph\, then there are finitely many 4-critical H-free graphs if and onl
 y if H is a subgraph of P 6 . This answers a question of Seymour.      The 
 proof of our main result involves two distinct automatic proofs\, and an ex
 tensive structural analysis by hand.     In this talk we will mainly focus 
 on the algorithmic results by presenting a new algorithm for generating all
  minimal forbidden subgraphs to k-colourability for given graph classes. Th
 is algorithm (combined with new theoretical results) has been successfully 
 applied to fully characterise all forbidden subgraphs for k-colourability f
 or various classes of graphs without long induced paths.     (This is joint
  work with Maria Chudnovsky\, Oliver Schaudt and Mingxian Zhong.)  
DTSTAMP:20181105T173500
DTSTART:20181029T160000
CLASS:PUBLIC
LOCATION:Technische Universität Berlin Institut für Mathematik Straße des 1
 7. Juni 136 10623 Berlin Room MA 041 (Ground Floor)
SEQUENCE:0
SUMMARY:Jan Goedgebeur (Ghent University): Obstructions for 3-colouring gra
 phs with one forbidden induced subgraph
UID:92313411@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20181029-C-Goe
 dgebeur.html
END:VEVENT
END:VCALENDAR