[Facets-of-complexity] Invitation to Monday Colloquium - October 29th 2018

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

You are cordially invited to our next Monday Colloquium on October 29th at 16:00 h at TU Berlin.

Location:

Room MA 041 - Ground Floor
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.

This is joint work with Maria Chudnovsky, Oliver Schaudt and Mingxian Zhong.

Exceptionally, there will be no lecture and only this colloquium, because of the 'Einstein Workshop'.