Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: k-Colour partitions of acyclic tournaments. | k-Colour partitions of acyclic tournaments Paulo Barcia Universidade Nova de Lisboa Faculdade de Economia Campus de Campolide 1099-032 Lisboa Portugal barcia@ J. Orestes Cerdeira Instituto Superior de Agronomia Univ. Tecnica de Lisboa Tapada da Ajuda 1349-017 Lisboa Portugal orestes@ Submitted Jun 27 2002 Accepted Aug 21 2004 Published Jan 7 2005 Mathematics Subject Classifications 05C20 52B05 Abstract Let G1 be the acyclic tournament with the topological sort 0 1 2 n n 1 defined on node set N u 0 n 1 where N 1 2 . n . For integer k 2 let Gk be the graph obtained by taking k copies of every arc in G1 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 Gk 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 k2n2k 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. 1 Introduction Let G1 be the acyclic tournament with the topological sort 0 1 2 n n 1 dehned on node set N u 0 n 1 where N 1 2 . n . The arcs of G1 are therefore the pairs i j with i j. Given an integer k 2 consider the di graph Gk obtained by This author s research was financially supported by the Portuguese Foundation for Science and Technology FCT THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R5 1 taking k copies of every arc in G1 and colouring every copy with one of k different colours. A .
