# Difficulty of graph coloring and independent set?

Given a graph on $$n$$ vertices it is strongly $$NP$$-complete to decide it is $$3$$-colorable while it is easy to decide it is $$n$$-colorable.

1. Is there a parsimonious reduction from SUBSET-SUM to GRAPH-3-COLORABILITY or K-INDEPENDENT SET?

2. Is there a deterministic reduction from GRAPH-3-COLORABILITY to UNAMBIGUOUS-GRAPH-3-COLORABILITY or K-INDEPENDENT SET to UNMAMBIGUOUS-K-INDEPENDENT SET?

• This is a bit of a strange question. Polynomial time separations can be crossed by changing computer architecture, so I think you'd have to be very specific about what context you want a polynomial separation to hold on. Apr 23 '19 at 21:10
• Pragmatically speaking, a polynomial time separation in a cryptographic scheme is a sign that the scheme doesn't work for usual purposes. Apr 23 '19 at 21:10
• I think it's better to stick to a single question, not a list of questions. I also think it's better to start a new question rather than change an old one into something completely different. Aug 4 '19 at 10:12
• In planar graphs 6 coloring is trivial, and 4 coloring is doable in polynomial time, but 3 coloring is hard. So I don't see if there is any point to define a function like f(n), as for example in complete graphs it should be at least n and in planar graphs it should be a constant. Aug 4 '19 at 13:42
• Simplified posting.
– VS.
Aug 5 '19 at 22:38