Question 2[10]. Let G be a graph with n vertices. The k-coloring problem is to decide whether the vertices of G can be l

[answerhappygod]

Question 2 10 Let G Be A Graph With N Vertices The K Coloring Problem Is To Decide Whether The Vertices Of G Can Be L 1 (106.39 KiB) Viewed 136 times

Question 2[10]. Let G be a graph with n vertices. The k-coloring problem is to decide whether the vertices of G can be labeled from the set {1, 2, ..., k} such that for every edge (vw) in the graph, the labels of v and w are different. Is the (n-4)-coloring problem in P or in NP? Give a formal proof for your answer. A 'Yes' or 'No' answer is not sufficient to get a non- zero mark on this question.