School Seminars and Colloquia

Minimum partition of an independence system

ORSUM Seminar

by Dr Sanming Zhou


Institution: The University of Melbourne
Date: Thu 6th November 2008
Time: 1:00 PM
Location: Room 213, Richard Berry Bldg, The University of Melbourne

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 mfackrel@ms.unimelb.edu.au