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 Erdos-Hajnal conjecture.