Is Graph 2-Coloring NP-Complete? I know there is a polynomial time algorithm for 2-coloring. But should the answer be "No" or should it be "Maybe"?
Since 2-coloring is in NP and we dont know if there is a reduction of any NP-complete to 2-color.
Since graph 2-coloring is in P and it is not the trivial language ($\emptyset$ or $\Sigma^*$), it is NP-complete if and only if P=NP.