============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

             Minioficina de Combinatória
============================================================

Título:      The chromatic thresholds of graphs
            
Palestrante: Simon Griffiths
             Instituto de Matemática Pura e Aplicada

Hora e Data: 14h, quinta-feira, 08 de setembro de 2011

Local:       auditório do NUMEC

Resumo: 

The chromatic threshold  of a graph H is  the infimum over d
such that  the chromatic number H-free graph  G with minimum
degree  at  least d|G|  is  bounded.   Erdös and  Simonovits
conjectured  in 1973  that  the chromatic  threshold of  the
triangle is 1/3,  and this was proved in  2002 by Thomassen.
In a recent breakthrough  Luczak and Thomassé determined the
chromatic threshold for a  large class of 3-chromatic graphs
using the new concept of paired VC-dimension.

In this work, we determine the chromatic threshold of every
graph H.

This is joint work with Peter Allen (USP), Julia Böttcher
(USP), Yoshiharu Kohayakawa (USP) and Rob Morris (IMPA).