Your query: an = (927.68063)
Answers 1-1 (of 1)
[New query form]
927.68063
Brandstaedt, Andreas; Le, Van Bang; Szymczak, Thomas
The complexity of some problems related to GRAPH 3-COLORABILITY. (English)
[J] Discrete Appl. Math. 89, No.1-3, 59-73 (1998). [ISSN 0166-218X]
It is well-known that the graph 3-colorability problem, deciding whether a given graph has a stable set whose deletion results in a bipartite graph, is NP-complete. We prove the following related theorems: It is NP-complete to decide whether a graph has a stable set whose deletion results in (1) a tree or (2) a trivially perfect graph, and there is a polynomial algorithm to decide if a given graph has a stable set whose deletion results in (3) the complement of a bipartite graph, (4) a split graph or (5) a threshold graph.
- MSC 1991:
-
*68R10 Graph theory in connection with computer science
68Q25 Analysis of algorithms and problem complexity
05C15 Chromatic theory of graphs and maps
Keywords: graph 3-colorability problem
Cited in Zbl. reviews...
[New query form]Answers 1-1 (of 1)
Zentralblatt MATH,
Copyright (c) 2000 European Mathematical Society, FIZ Karlsruhe & Springer-Verlag.