Discrete Mathematics and Optimization Seminar

---

Maria Chudnovsky
Princeton University/CMI
Thursday February 9th at 4pm
Burnside 920



Title. The structure of bull-free graphs.

Abstract. A bull is a graph consisting of a triangle and two pendant edges. A graph is
said to be bullfree if it contains no induced subgraph isomorphic to a bull.
An obvious example of a bull free graph is a graph with no triangle, or a graph with no
stable set of size three; but there are others. It turns out, however, that all bullfree
graphs can be built starting from graphs that belong to a few basic classes, and gluing
them together by certain operations; and this is the main topic of this talk. Using
this structure theorem, in joint work with S. Safra, we were able to prove that in every
bull free graph there is either a stable set or a clique containing at least
|V(G)|^(1/4) vertices, thus settling the Erdos-Hajnal conjecture for the bull.