Deletion and editing to RBMGs are NP-hard; 2-colored editing is FPT via bicluster editing reduction; modification to hierarchically colored cographs is NP-complete.
Hierarchical Colorings of Cographs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Cographs are exactly hereditarily well-colored graphs, i.e., the graphs for which a greedy coloring of every induced subgraph uses only the minimally necessary number of colors $\chi(G)$. In recent work on reciprocal best match graphs so-called hierarchically coloring play an important role. Here we show that greedy colorings are a special case of hierarchical coloring, which also require no more than $\chi(G)$ colors.
fields
cs.CC 1years
2019 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Complexity of Modification Problems for Reciprocal Best Match Graphs
Deletion and editing to RBMGs are NP-hard; 2-colored editing is FPT via bicluster editing reduction; modification to hierarchically colored cographs is NP-complete.