The black-and-white coloring problem on distance-hereditary graphs and strongly chordal graphs

DOI10.1007/978-3-642-29700-7_31zbMATH Open1304.05048arXiv1111.0867OpenAlexW1528573371WikidataQ62041796 ScholiaQ62041796MaRDI QIDQ2898008FDOQ2898008

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

Publication date: 16 July 2012

Published in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1111.0867

Recommendations

• On the complexity of the black-and-white coloring problem on some classes of perfect graphs
• The black-and-white coloring problem on chordal graphs
• The Black-and-White Coloring Problem on Trees
• An improved algorithm for the black-and-white coloring problem on trees
• Splitting trees

zbMATH Keywords

interval graphscographsdistance-hereditary graphsstrongly chordal graphsthreshold graphsblack-and-white coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cited In (4)

• An improved algorithm for the black-and-white coloring problem on trees
• On the complexity of the black-and-white coloring problem on some classes of perfect graphs
• The black-and-white coloring problem on chordal graphs
• The Black-and-White Coloring Problem on Trees

This page was built for publication: The black-and-white coloring problem on distance-hereditary graphs and strongly chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2898008)