Eigenvalues of K1, k‐Free Graphs and the Connectivity of Their Independence Complexes. Issue 4 (20th November 2015) - Aharoni, Ron; Alon, Noga; Berger, Eli
Abstract: Let G be a graph on n vertices, with maximal degree d, and not containing K 1, k as an induced subgraph. We prove: 1. λ ( G ) ≤ ( 2 − 1 2 k − 2 + o ( 1 ) ) d 2. η ( I ( G ) ) ≥ n ( k − 1 ) d ( 2 k − 3 ) + k − 1 . Here λ ( G ) is the maximal eigenvalue of the Laplacian of G, I ( G ) is the independence complex of G, and η ( C ) denotes the topological connectivity of a complex C plus 2. These results provide improved bounds for the existence of independent transversals in K 1, k ‐free graphs.