The Domatic Number Problem on Some Perfect Graph Families
Lists
Only you see this
Abstract
An extremely simple, linear time algorithm is given for constructing a domatic partition in totally balanced hypergraphs. This simplifies and generalizes previous algorithms for interval and strongly chordal graphs. On the other hand, the domatic number problem is shown to be NP-complete for several families of perfect graphs, including chordal and bipartite graphs.
BibTeX
@inproceedings{kaplan1994domatic,
author = {Haim Kaplan and Ron Shamir},
title = {{The Domatic Number Problem on Some Perfect Graph Families}},
booktitle = {Inf. Process. Lett},
year = {1994},
url = {https://openreview.net/forum?id=k-nZ16WHjxI},
}Loading related content...