TRANSVERSAL PARTITIONING IN BALANCED HYPERGRAPHS

A transversal of a hypergraph is a set of vertices meeting all the hyp eredges. A k-fold transversal Omega of a hypergraph is a set of vertic es such that every hyperedge has at least k elements of Omega. In this paper, we prove that a k-fold transversal of a balanced hypergraph ca n be expressed as a union of k pairwise disjoint transversals and such partition can be obtained in polynomial time. We give an NC algorithm to partition a k-fold transversal of a totally balanced hypergraph in to k pairwise disjoint transversals. As a corollary, we deduce that th e domatic partition problem is in polynomial class for chordal graphs with no induced odd trampoline and is in NC-class for strongly chordal graphs.