A Note on an NP-Complete Problem,
J. L. Lewandowski · Defense Technical Information Center (DTIC) · 1979
We show in this note that the problem of two-coloring a graph G = (V, E) with a distinguished vertex p and two distinguished subset A (p) and B (p) of V, such that there is a red connected subgraph containing A + p, and a blue connected subgraph containing B + p, is NP-Complete. We prove this by reduction of 3-satisfiability by constructing, for a given boolean expression in disjunctive normal form with three variables in each term, a graph G with a distinguished vertex D and two subsets a (D) and B (D) such that the expression is satisfiable if and only if the graph has a two-coloring with the desired monochromatic subtrees. (Author)