\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Stefan Gr\"{u}newald, Peter J. Humphries and Charles Semple}
%
%
\medskip
\noindent
%
%
{\bf Quartet Compatibility and the Quartet Graph}
%
%
\vskip 5mm
\noindent
%
%
%
%
A collection ${\cal P}$ of phylogenetic trees is compatible if there exists
a single phylogenetic tree that displays each of the trees in
${\cal P}$. Despite its computational difficulty, determining the
compatibility of ${\cal P}$ is a fundamental task in evolutionary
biology. Characterizations in terms of chordal graphs have been
previously given for this problem as well as for the closely-related
problems of (i)~determining if ${\cal P}$ is definitive and
(ii)~determining if ${\cal P}$ identifies a phylogenetic tree. In this
paper, we describe new characterizations of each of these problems in
terms of edge colourings. Furthermore, making use of the tools that
underlie these new characterizations, we also determine the minimum
number of quartets required to identify an arbitrary phylogenetic
tree, thus correcting a previously published result.

\bye

.
