{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:28Z","timestamp":1753893808282,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>Let $G_{1}$ be the acyclic tournament with the topological sort $0 &lt; 1 &lt; 2 &lt; \\dots &lt; n &lt; 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&gt;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.<\/jats:p>","DOI":"10.37236\/1902","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T00:19:41Z","timestamp":1578701981000},"source":"Crossref","is-referenced-by-count":0,"title":["$k$-Colour Partitions of Acyclic Tournaments"],"prefix":"10.37236","volume":"12","author":[{"given":"Paulo","family":"Barcia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Orestes","family":"Cerdeira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2005,1,7]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v12i1r5\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v12i1r5\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T23:51:38Z","timestamp":1579305098000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v12i1r5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1,7]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,1,7]]}},"URL":"https:\/\/doi.org\/10.37236\/1902","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2005,1,7]]},"article-number":"R5"}}