Rutgers Discrete Mathematics Seminar

Title: The Algebraic and Topological Properties of Claw-free Graphs

Speaker: Eli Berger, Haifa University

Date: Wednesday, September 25, 2013 3:00pm ***

Location: Hill Center, Room 425, Rutgers University, Busch Campus, Piscataway, NJ

***Note special day, room and time


We study two parameters that can be associated with a given graph. The first parameter is an algebraic one: the maximal eigenvalue of the Laplacian. The second parameter is a topological one: the connectivity of the simplicial complex of independent sets. These two parameter are useful in studying combinatorial properties of the graph, such as the existence of independent transversals. In a previous work with Aharoni and Meshulam, we showed that these two parameters are related. In this talk we show that for claw-free graphs we can obtained bounds for these parameters that are better than the ones known for general graphs. similar results are obtained for $K_{1,k}$-free$ graphs for any k. This is joint work with Noga Alon and Ron Aharoni.