KAIST Discrete Math Seminar

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