@inproceedings{f20f06400e114e3ea250fd717eb13622,
title = "The black-and-white coloring problem on distance-hereditary graphs and strongly chordal graphs",
abstract = "Given a graph G and integers b and w. The black-and-white coloring problem asks if there exist disjoint sets of vertices B and W with |B|=b and |W|=w such that no vertex in B is adjacent to any vertex in W. In this paper we show that the problem is polynomial when restricted to cographs, distance-hereditary graphs, interval graphs and strongly chordal graphs. We show that the problem is NP-complete on splitgraphs.",
keywords = "Black-and-white coloring, Cographs, Distance-hereditary graphs, Interval graphs, Strongly chordal graphs, Threshold graphs",
author = "Ton Kloks and Poon, {Sheung Hung} and Tsai, {Feng Ren} and Wang, {Yue Li}",
year = "2012",
doi = "10.1007/978-3-642-29700-7_31",
language = "English",
isbn = "9783642296994",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "339--350",
booktitle = "Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Proceedings",
note = "6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012 ; Conference date: 14-05-2012 Through 16-05-2012",
}