Maria Chudnovsky, Packing seagulls in graphs with no stable set of size three

Packing seagulls in graphs with no stable set of size three
Maria Chudnovsky
Department of Industrial Engineering and Operations Research & Department of Mathematics, Columbia University, New York, USA
2009/5/21 Thursday 2PM-3PM

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


Comments are closed.