\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
\nopagenumbers
\noindent
%
%
{\bf Paulo Barcia and J. Orestes Cerdeira}
%
%
\medskip
\noindent
%
%
{\bf $k$-Colour Partitions of Acyclic Tournaments}
%
%
\vskip 5mm
\noindent
%
%
%
%
Let $G_{1}$ be the acyclic tournament with the topological sort
$0<1<2<\dots<n<n+1$ defined on node set $N\cup \{0,n+1\}$, where
$N=\{1,2,\dots,n\}$. For integer $k\geq 2$, let $G_{k}$ be the graph
obtained by taking $k$ copies of every arc in $G_{1}$ and colouring
every copy with one of $k$ different colours.  A $k$-colour partition
of $N$ is a set of $k$ paths from 0 to $n+1$ such that all arcs of
each path have the same colour, different paths have different
colours, and every node of $N$ is included in exactly one path.  If
there are costs associated with the arcs of $G_{k}$, the cost of a
$k$-colour partition is the sum of the costs of its arcs.  For
determining minimum cost $k$-colour partitions we describe an
$O(k^{2}n^{2k})$ algorithm, and show this is an NP-$hard$ problem.  We
also study the convex hull of the incidence vectors of $k$-colour
partitions.  We derive the dimension, and establish a minimal equality
set.  For $k>2$ we identify a class of facet inducing inequalities.
For $k=2$ we show that these inequalities turn out to be equations,
and that no other facet defining inequalities exists besides the
trivial nonnegativity constraints.

\bye

.