Minimum partition of an independence system
by Dr Sanming Zhou
Abstract: An independence system is a set E together with a family J of subsets, called independent, of E such that any subset of an independent set is also independent. In terms of combinatorial topology, an independence system is a simplicial complex. Given a finite independence system (E, J), the Minimum Partition Problem (MPP) seeks a partition of E into the least number of independent sets. This fundamental problem provides a unifying framework for a number of combinatorial optimisation problems, including various conditional colouring problems for graphs. The smallest integer n such that E can be partitioned into n independent sets is called the J-chromatic number of E. We will talk about connections between MPP and a few other well-studied optimisation problems and a sequential colouring algorithm. In particular, by showing that the J-chromatic number is equal to the domination number of a split graph associated with (E, J), we give a few upper bounds on the J-chromatic number of E in terms of some basic invariants of (E, J).
For More Information: Mark Fackrell email@example.com