Transversal partitioning in balanced hypergraphs

✍ Scribed by Elias Dahlhaus; Jan Kratochvíl; Paul D. Manuel; Mirka Miller

• Book ID: 104294800
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 958 KB
• Volume: 79
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(97)00034-6

✦ Synopsis

A transversal of a hypergraph is a set of vertices meeting all the hyperedges. A k-fold transversal 52 of a hypergraph is a set of vertices such that every hyperedge has at least k elements of R. In this paper, we prove that a k-fold transversal of a balanced hypergraph can 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 into k pairwise disjoint transversals. As a corollary, we deduce that the domatic partition problem is in polynomial class for chordal graphs with no induced odd trampoline and is in NC-class for strongly chordal graphs.