The structure of bullfree graphs
The structure of bullfree graphs

Maria Chudnovsky, Columbia University and Clay Mathematics Institute (CMI)
Fine Hall 314
The bull is a graph consisting of a triangle and two disjoint pendant edges. Obvious examples of bullfree graphs are graphs with no triangle, or graphs with no stable set of size three. But there are others (for example, substituting one bullfree graph into another produces a bullfree graph). It turns out, however, that one can explicitly describe all bullfree graphs that cannot be constructed from smaller ones by substitutions. In this talk we will discuss this construction. We will also mention the connection with the ErdosHajnal conjecture.