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 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.
Bio:
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. .