[Todos] Seminario de Optimización y Grafos 2009: Maria Chudnovsky (martes a las 16)

[Guillermo Duran]

Invitamos a todos al Seminario de Optimización y Grafos, edición 2009, del
grupo de investigación en Teoría de Grafos y Optimización Combinatoria
(http://www.dc.uba.ar/inv/grupos/grafos)
de los departamentos de Computación y Matemática de la FCEN, UBA y el
Instituto de Ciencias de la UNGS.

La primer charla del Seminario de este año estará a cargo de Maria
Chudnovsky (Profesora Asociada de Columbia University, USA).

Maria Chudnovsky (http://www.columbia.edu/~mc2775/) está pasando unos días
como profesora invitada en el Departamento de Matemática de la Facultad y
es Profesora Asociada de Columbia University (USA). A pesar de su corta
edad, ha publicado muy importantes trabajos en las principales revistas de
Combinatoria y Teoría de Grafos, y es una de las figuras de más renombre a
nivel internacional en nuestra área. Su trabajo más importante (en
coautoría con N. Robertson, P. Seymour y R. Thomas), la resolución de la
Conjetura de los Grafos Perfectos, abierta por más de 40 años, ha sido
publicado en 2006 en el Annals of Mathematics.

Los invitamos entonces para este martes a las 16 hs. en el aula E-24 del
Pabellon I.

Title: Packing Seagulls

Abstract:

Hadwiger's conjecture is a well known open problem in graph theory. It
states that every graph with chromatic number $k$, contains a certain
structure, called a "clique minor" of size $k$. An interesting special
case of the conjecture, that is still wide open, is when the graph $G$
does not contain three pairwise non-adjacent vertices. In this case, it
should be true that $G$ contains a clique minor of size $t$ where $t =
\lceil |V(G)|/2 \rceil$. This remains open, but Jonah Blasiak proved it in
the subcase when $|V(G)|$ is even and the vertex set of $G$ is the union
of three cliques. Here we prove a strengthening of Blasiak's result: that
the conjecture holds if some clique in $G$ contains strictly more than
$|V(G)|/4$ vertices.

This is a consequence of a result about packing ``seagulls''. A {\em
seagull } in $G$ is an induced three-vertex path. Deciding if a graph
contains $k$ pairwise disjoint seagulls is NP-complete in general (this is
a result of Dor and Tarsi), but for graphs with no three pairwise
non-adjacent vertices, there is a nice theorem, and a polynomial time
algorithm.

This is joint work with Paul Seymour.