Colloquium 2017

- Campus Jussieu

Le colloquium Pierre et Marie Curie présente des exposés consacrés à la physique contemporaine et aux disciplines connexes. Ces exposés sont destinés à tous les étudiants et à tous les enseignants et chercheurs mais plus particulièrement aux étudiants de master et aux étudiants en thèse. Les exposés ont lieu soit en français soit en anglais.

Induced subgraphs and coloring


Envie de télécharger cette vidéo sur votre ordinateur ? Cliquez ici (poids : 1.3 Go)

Résumé

What causes a graph to have high chromatic number? One reason is that the graph may contain a large set of pairwise adjacent vertices (called a "clique"), but what can be said if that is not the case? Around 1985 Andras Gayfas made three conjectures about structures that must be present in a graph with large chromatic number all of whose cliques have bounded size. Recently, in joint work with Alex Scott, Paul Seymour and Sophie Sprikl we proved the strongest of these conjectures, that implies the other two. In this talk we will discuss some of the proof ideas, and related problems and theorems.


Orateur(s) : Maria Chudnovsky Princeton University
Public : Tous
Date : 25 avril 2017
Lieu : Campus Jussieu