# All but Five Three Colorable

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.

• @YuvalFilmus: Can you suggest a reduction? I have a proposal, but I dont want to contaminate the readers thought by my proposal. – ARK Dec 5 '14 at 3:19
• I suggested a reduction in my answer. But generally on this site we appreciate people showing effort on solving their questions on their own. For example, if you have a proposed reduction but can't prove that it works, you could share it with us. – Yuval Filmus Dec 5 '14 at 3:25
• (Polynomial time) many-one reductions are the ones appearing in the definition of NP-hardness. If you look at any textbook or lecture notes (or even Wikipedia) on NP-hardness, I'm sure you'll find a definition and examples. – Yuval Filmus Dec 5 '14 at 4:21
• Why do you doubt your approach? Do you have a specific question, i.e. one distinct from "please grade my hand-in"? – Raphael Dec 5 '14 at 11:38
• @user10584 That's fine, but simply not what SE is suitable for. – Raphael Dec 5 '14 at 18:25