k-Colour partitions of acyclic tournaments

Research output: Contribution to journalArticle

Abstract

Let G1 be the acyclic tournament with the topological sort 0 < 1 < 2 < < n < n + 1 de ned on node set N [ f0; n + 1g, where N = f1; 2; : : : ; ng. For integer k k dierent 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, dierent paths have dierent 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 de ning inequalities exists besides the trivial nonnegativity constraints.2, let Gk be the graph obtained by taking k copies of every arc in G1 and colouring every copy with one of
Original languageEnglish
Pages (from-to)1-12
JournalElectronic Journal Of Combinatorics
Volume12
Issue number1
Publication statusPublished - 1 Jan 2005

Fingerprint Dive into the research topics of 'k-Colour partitions of acyclic tournaments'. Together they form a unique fingerprint.

  • Cite this