MIT Combinatorics Seminar The Structure Of Bullfree Graphs Maria Chudnovsky, (Princeton/CMI) Thursday, November 10, 2005   4:15 pm    Room 2-142 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 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)|^\delta vertices, thus settling the Erdos-Hajnal conjecture for the bull