Extending the Gyarfas-Sumner Conjecture
speaker: Maria Chudnovsky (Columbia University )abstract: The "co-chromatic number" of a graph G is the smallest number t, such that V(G) can be partitioned into t cliques and stable sets. Which graphs have bounded co-chromatic number? Let us say that a family F of graphs is "heroic" if every graph G with no induced subgraph isomorphic to a member of F has bounded co-chromatic number (where the bound depends on F). Assuming an old conjecture of Gyarfas and Sumner, we can completely characterize all finite heroic families.
The proof relies on the following result. A graph G is "k-split" if V(G) can be partitioned into two sets A and B, such that A contains no clique of size k+1, and B contains no stable set of size k+1. Our first result is that for every k, the minimal non-k-split graphs have bounded size. As a consequence, we show that for every complete multipartite graph H1, and every complement of a complete multipartite graph H2, there exists k, such that every graph G with no induced subgraph isomorphic to H1 or H2 is k-split. This is joint work with Paul Seymour.
In the final part of the talk, we will discuss recent extensions of this theorem, obtained in joint work with Alex Scott and Paul Seymour, where instead of excluding a complete multipartite graph and the complement of one, two general cographs are excluded.
timetable:
Mon 3 Sep, 9:00 - 10:00, Aula Dini
<< Go back