An NP Problem Named All But Five Three Colorable(AB53C) is defined as follows :- Input : Connected Graph G(V,E) The Connected Graph is AB53C, iff the Given Graph is 3-Colorable by leaving UPTO 5 Vertices Uncolored.
Question:- The Problem is in NP. Show the reduction from 3-Colorable Problem.
The Proposed Solution is :-
Find Permutation of All Subsets where |V'| = |V| - 5. Basically these subsets will have 5 vertices less than the original set. Remove all edges from V' to V. All such subsets are found out and then passed through the 3-Color. If we get YES on any one of these Subgraphs, then we have a AB53C.
I want someone disprove my method OR show that the reduction is non-polynomial. Otherwise, my proposal is correct.