Chennai Mathematical Institute

Seminars




3:30 pm, Seminar Hall
2-divisibility and perfect divisibility in graphs

Vaidyanathan Sivaraman
SUNY Binghamton.
29-08-17


Abstract

A graph G is 2-divisible 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 2-divisible graphs and perfectly divisible graphs is in the context of chi-boundedness. In this talk we discuss the proofs of the following theorems.

Theorem 1. If G is (P_5, C_5)-free, then G is 2-divisible. Theorem 2. If G is bull-free and either P_5-free or odd-hole-free, then G is perfectly divisible.

This is joint work with Maria Chudnovsky.