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

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

Research output: Chapter in Book/Conference proceedingConference contributionpeer-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, distance-hereditary graphs, interval graphs and strongly chordal graphs. We show that the problem is NP-complete on splitgraphs.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Proceedings
Pages339-350
Number of pages12
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012 - Beijing, China
Duration: 14 May 201216 May 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7285 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012
Country/TerritoryChina
CityBeijing
Period14/05/1216/05/12

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

Fingerprint

Dive into the research topics of 'The black-and-white coloring problem on distance-hereditary graphs and strongly chordal graphs'. Together they form a unique fingerprint.

Cite this