Title: Nearly-linear stable sets
| Speaker: | Paul Seymour |
| Affiliation: | Princeton University |
| Location: | QNC 0101 |
Abstract: The Gyárfás-Sumner conjecture says that for every forest 𝐻 and complete graph 𝐾, there exists 𝑐 such that every {𝐻,𝐾}-free graph (that is, containing neither of 𝐻,𝐾 as an induced subgraph) has chromatic number at most 𝑐. This is still open, but we have proved that every {𝐻,𝐾}-free graph 𝐺 has chromatic number at most |𝐺| 𝑜(1) .
Second, a “multibroom” is a graph obtained from a tree of radius two by subdividing (arbitrarily) the edges incident with the root of the tree. It is not known that all multibrooms satisfy the Gyárfás-Sumner conjecture, but we have proved that they satisfy it with “chromatic number” replaced by “fractional chromatic number”.
Third, fix a graph 𝐻 and a clique 𝐾, and suppose that 𝐺 is a 𝐾-free graph that contains no subdivision of 𝐻 as an induced subgraph. The chromatic number of 𝐺 need not be bounded, but we have proved that it is at most |𝐺| 𝑜(1) (and the same is true if we only exclude 𝐾 and subdivisions of 𝐻 in which each edge is subdivided at most 𝑂(log |𝐺|) times).
These results are all proved by finding linear or nearly-linear stable sets of vertices. We will survey this material and sketch some of the proofs (assuming it doesn't all fall down – these results were only proved a few days ago).
Joint work with Tung Nguyen and Alex Scott.
This seminar is a special Tutte Colloquium offered as part of the Fulkerson 100 Workshop.