罢颈迟濒别:听Nearly-linear stable sets
| Speaker: | Paul Seymour |
| Affiliation: | Princeton University |
| Location: | QNC 0101 |
础产蝉迟谤补肠迟:听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 鈥渕ultibroom鈥 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 鈥渃hromatic number鈥 replaced by 鈥渇ractional 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.