[Todos] Recordatorio: Coloquios del Departamento de Matemática (jueves 6/8/09)

[Daniel Carando]

Próximo coloquio:
Hoy jueves 6 de agosto a las 16:00, aula E24

Maria Chudnovsky
Columbia University

Perfect Graphs --- structure and recognition

Resumen: A graph is called perfect if for every induced subgraph, the
size of its largest clique equals the minimum number of colors needed
to color its vertices. As it turns out, the notion of perfect graphs
generalizes a large number of phenomena, both in graph theory and in
combinatorial optimization. Therefore, the problems of charactering
perfect (or minimal imperfect)   graphs and finding an efficient
recognition algorithm  have become well  known in both  communities.
In 1960's Claude Berge made a onjecture that any graph with no induced
odd cycles of length greater than three or their complements is
perfect (thus, odd cycles of length greater than three and their
complements are the only minimal imperfect graphs). This conjecture is
know as the Strong Perfect Graph Conjecture.
We call graphs containing no induced odd cycles of length greater than
three or their complements Berge graphs. A stronger conjecture was
made by Conforti, Cornuejols and Vuskovic, that any Berge graph either
belongs to one of a few well understood basic classes or has a
decomposition that can not occur in a minimal counterexample to
Berge's Conjecture.
In joint work with Neil Robertson, Paul Seymour and Robin Thomas we
were able to prove this conjecture and consequently the Strong Perfect
Graph Theorem.
Later, in joint work with G. Cornuejols, X, Lui, P.Seymour and K.
Vuskovic, we found an algorithm that tests in polynomial time whether
a graph is Berge, and therefore perfect.
In my talk I will give an overview of both these results.

Están todos cordialmente invitados.

Daniel Carando


http://mate.dm.uba.ar/~dcarando/coloquios/