Theory of excluding induced subgraphs
Paul Seymour Department of Mathematics, Princeton University, Princeton, NJ, USA
Maria Chudnovsky, Columbia University, New York, NY, USA
2014/12/11 Thu 10:30AM-12PM, 1:30PM-3PM
2014/12/12 Fri 10:30AM-12PM, 1:30PM-3PM
E6-1, Room 1501
2014/12/12 Fri 10:30AM-12PM, 1:30PM-3PM
E6-1, Room 1501
This will be a series of four lectures, beginning with a general introduction to the area of induced subgraphs, and later focusing on several recent results. We will examine the structure of graphs that do not contain certain induced subgraphs, and in particular study relations between the clique number, stability number and chromatic number of these graphs. Later topics will include the strong perfect graph theorem, and recent progress on the Erdos-Hajnal conjecture, and on various conjectures of Gyárfás.
for each 
, where 
is the set of edges incident to v. The fractional matching number of G, written 
, is the maximum of 
over all fractional matchings f. Let G be an n-vertex graph with minimum degree d, and let 
be the largest eigenvalue of G. In this talk, we prove that if k is a positive integer and ![\lambda_1(G) < d\sqrt{1+\frac{2k}{n-k}}[/latex], then [latex]\alpha'_*(G) > \frac{n-k}{2}](https://s0.wp.com/latex.php?latex=%5Clambda_1%28G%29+%3C+d%5Csqrt%7B1%2B%5Cfrac%7B2k%7D%7Bn-k%7D%7D%26%2391%3B%2Flatex%26%2393%3B%2C+then+%26%2391%3Blatex%26%2393%3B%5Calpha%27_%2A%28G%29+%3E+%5Cfrac%7Bn-k%7D%7B2%7D&bg=ffffff&fg=000000&s=0 "\lambda_1(G) < d\sqrt{1+\frac{2k}{n-k}}[/latex], then [latex]\alpha'_*(G) > \frac{n-k}{2}")
.