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.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20181029-C-Goedgebeur.html
END:VEVENT
END:VCALENDAR