MIT Combinatorics Seminar
The Structure Of Bullfree Graphs
Maria Chudnovsky, (Princeton/CMI)
Thursday, November 10, 2005 4:15 pm Room 2142
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 ErdosHajnal conjecture
for the bull


