You are cordially invited to our next Monday Colloquium on
October 29th at 16:00 h at TU Berlin. Location: Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin Time: Monday, October 29th - 16:00 h Colloquium: Jan Goedgebeur (Ghent University) Title: Obstructions for 3-coloring graphs with one forbidden induced subgraph Abstract: For several graph classes without long induced paths there
exists 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 P6-free graphs, and give the complete list that
consists of 24 graphs. In particular, we obtain a certifying
algorithm for 3-colouring P6-free graphs, which solves an open
problem posed by Golovach et al. (Here, P6 denotes the induced
path on six vertices.) Our result leads to the following dichotomy
theorem: if H is a connected graph, then there are finitely many
4-critical H-free graphs if and only if H is a subgraph of P6.
This answers a question of Seymour. The proof of our main result
involves two distinct automatic proofs, and an extensive
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. This algorithm (combined with new theoretical
results) has been successfully applied to fully characterise all
forbidden subgraphs for k-colourability for various classes of
graphs without long induced paths. Exceptionally, there will be no lecture and only this colloquium, because of the 'Einstein Workshop'. |