Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656923 | Journal of Combinatorial Theory, Series B | 2012 | 31 Pages |
The bull is a graph consisting of a triangle and two pendant edges. A graph is called bull-free if no induced subgraph of it is a bull. This is a summary of the last two papers [2] and [3] in a series [1], [2] and [3] (Chudnovsky, 2012). The goal of the series is to give a complete description of all bull-free graphs. We call a bull-free graph elementary if it does not contain an induced three-edge-path P such that some vertex c∉V(P)c∉V(P) is complete to V(P)V(P), and some vertex a∉V(P)a∉V(P) is anticomplete to V(P)V(P). Here we prove that every elementary graph either belongs to one of a few basic classes, or admits a certain decomposition, and then uses this result together with the results of [1] ( this issue) to give an explicit description of the structure of all bull-free graphs.