On the complexity of the black-and-white coloring problem on some classes of perfect graphs
DOI10.1016/j.tcs.2013.10.024zbMath1418.68104OpenAlexW2008684633WikidataQ62041756 ScholiaQ62041756MaRDI QIDQ2445872
Yue-Li Wang, Sheung-Hung Poon, Feng-Ren Tsai, Ton Kloks
Publication date: 15 April 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2013.10.024
distance-hereditary graphscographsinterval graphsstrongly chordal graphsthreshold graphsblack-and-white coloring
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Hypergraphs with no special cycles
- On rigid circuit graphs
- Graphs whose neighborhoods have no special cycles
- Characterizations of strongly chordal graphs
- A characterization of totally balanced hypergraphs
- Distance-hereditary graphs
- Complement reducible graphs
- Splitting trees
- On simple characterizations of k-trees
- Threshold graphs and related topics
- Triangulated graphs and the elimination process
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- The Black-and-White Coloring Problem on Trees
- Representation of a finite graph by a set of intervals on the real line
- Characterizations of totally balanced matrices
- The Complexity of the Partial Order Dimension Problem
- Totally-Balanced and Greedy Matrices
- A Linear Recognition Algorithm for Cographs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- The number of labeled k-dimensional trees
- The number of labeled k-trees
- A Characterization of Comparability Graphs and of Interval Graphs
- Difference graphs
- The NP-completeness column: An ongoing guide
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
