Page 1 of 1
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
Posted: Sat Nov 27, 2021 10:26 am
by 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 139 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.