Minimum partition of an independence system into independent sets

Given an independence system (E,P)(E,P), the Minimum Partition Problem (MPP) seeks a partition of EE into the least number of independent sets. This notion provides a unifying framework for a number of combinatorial optimisation problems, including various conditional colouring problems for graphs. The smallest integer nn such that EE can be partitioned into nn independent sets is called the PP-chromatic number of EE. In this article we study MPP and the PP-chromatic number with emphasis on connections with a few other well-studied optimisation problems. In particular, we show that the PP-chromatic number of EE is equal to the domination number of a split graph associated with (E,P)(E,P). With the help of this connection we give a few upper bounds on the PP-chromatic number of EE in terms of some basic invariants of (E,P)(E,P).