On the complexity of the black-and-white coloring problem on some classes of perfect graphs

Ton Kloks; Sheung Hung Poon; Feng Ren Tsai; Yue Li Wang

doi:10.1016/j.tcs.2013.10.024

On the complexity of the black-and-white coloring problem on some classes of perfect graphs

Ton Kloks, Sheung Hung Poon, Feng Ren Tsai, Yue Li Wang

Research output: Journal Publication › Article › peer-review

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, interval graphs, permutation graphs, distance-hereditary graphs, and strongly chordal graphs. We show that the problem is NP-complete on splitgraphs.

Original language	English
Pages (from-to)	51-63
Number of pages	13
Journal	Theoretical Computer Science
Volume	532
DOIs	https://doi.org/10.1016/j.tcs.2013.10.024
Publication status	Published - 2014
Externally published	Yes

Keywords

Black-and-white coloring
Cographs
Distance-hereditary graphs
Interval graphs
Strongly chordal graphs
Threshold graphs

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2013.10.024

Cite this

@article{02fa9770bf6a47d19ae3b48bd431c1f3,

title = "On the complexity of the black-and-white coloring problem on some classes of perfect 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, interval graphs, permutation graphs, distance-hereditary 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}",

note = "Publisher Copyright: {\textcopyright} 2013.",

year = "2014",

doi = "10.1016/j.tcs.2013.10.024",

language = "English",

volume = "532",

pages = "51--63",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - On the complexity of the black-and-white coloring problem on some classes of perfect graphs

AU - Kloks, Ton

AU - Poon, Sheung Hung

AU - Tsai, Feng Ren

AU - Wang, Yue Li

PY - 2014

Y1 - 2014

N2 - 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, interval graphs, permutation graphs, distance-hereditary graphs, and strongly chordal graphs. We show that the problem is NP-complete on splitgraphs.

AB - 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, interval graphs, permutation graphs, distance-hereditary graphs, and strongly chordal graphs. We show that the problem is NP-complete on splitgraphs.

KW - Black-and-white coloring

KW - Cographs

KW - Distance-hereditary graphs

KW - Interval graphs

KW - Strongly chordal graphs

KW - Threshold graphs

UR - http://www.scopus.com/inward/record.url?scp=85028095906&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2013.10.024

DO - 10.1016/j.tcs.2013.10.024

M3 - Article

AN - SCOPUS:85028095906

SN - 0304-3975

VL - 532

SP - 51

EP - 63

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

On the complexity of the black-and-white coloring problem on some classes of perfect graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this