Search Mailing List Archives
[theory-seminar] Theory Lunch 5/23 -- Nitya Mani
Weiyun Ma
wyma at stanford.edu
Mon May 20 13:23:51 PDT 2019
Hi everyone,
This Thursday at theory lunch, Nitya will tell us about "Max-k-Cuts in H-Free Graphs." (See abstract below.)
As always, please join us from noon to 1pm at 463A.
----------------------------------------------------------
Max-k-Cuts in H-Free Graphs
Speaker: Nitya Mani
We study the following question: how few edges can we delete from any H-free graph on n vertices in order to make the resulting graph k-colorable? It turns out that various classical problems in extremal combinatorics are special cases of this problem, and this quantity yields bounds on the Max-k-Cut of an H-free graph. For H any fixed odd cycle, we determine the answer up to a constant factor when n is sufficiently large. We also prove upper bounds when H is a clique or lies in some other families of graphs.
----------------------------------------------------------
Best,
Anna
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20190520/edb80e27/attachment-0001.html>
More information about the theory-seminar
mailing list