Compatibility, Incompatibility, Tree-Width, and Forbidden Phylogenetic Minors

A collection P of phylogenetic trees is compatible if there is a tree that displays all the relationships among species exhibited by the trees in P. We give a simple characterization of compatibility based on graph triangulation. We then study how to deal with incompatibility through edge contraction and tree deletion, and introduce the notion of a phylogenetic minor.