Packing seagulls in graphs with no stable set of size
three.

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 >= |V(G)|/2. 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 at least |V(G)|/4
vertices.

This is a consequence of a result about packing ``seagulls''. A seagull
in G is an induced three-vertex path. It is not known in general how to
decide in polynomial time whether a graph contains k pairwise disjoint
seagulls; but we answer this for graphs with no
stable sets of size three.

This is joint work with Paul Seymour.