3:30 pm, Seminar Hall 2divisibility and perfect divisibility in graphs Vaidyanathan Sivaraman SUNY Binghamton. 290817 Abstract A graph G is 2divisible if for every induced subgraph H of G, V(H) can be partitioned into two sets A, B such that the clique numbers of both H[A] and H[B] are smaller than that of H. A graph G is perfectly divisible if for every induced subgraph H of G, V(H) can be partitioned into two sets A, B such that H[A] is perfect and the clique number of H[B] is smaller than that of H. One reason to study 2divisible graphs and perfectly divisible graphs is in the context of chiboundedness. In this talk we discuss the proofs of the following theorems. Theorem 1. If G is (P_5, C_5)free, then G is 2divisible. Theorem 2. If G is bullfree and either P_5free or oddholefree, then G is perfectly divisible. This is joint work with Maria Chudnovsky.
