Question 16570 – Clique

Given an undirected graph G, an ordering σ of its vertices is called a perfect ordering if for every vertex v, the neighbours of v which precede v in σ form a clique in G. Recall that given an undirected graph G, a clique in G is a subset of vertices every two of which are connected by an edge, while a perfect coloring of G with k colors is an assignment of labels from the set {1, 2, . . . , k} to the vertices of G such that no two vertices which are adjacent in G receive the same label. Consider the following problems.,
Problem Special-Clique
INPUT: An undirected graph G, a positive integer k, and a perfect ordering σ of the vertices of G.
OUTPUT: Yes, if G has a clique of size at least k, No otherwise.
Problem Special-Coloring
INPUT: An undirected graph G, a positive integer k, and a perfect ordering σ of the vertices of G.
OUTPUT: Yes, if G has a proper coloring with at most k colors, No otherwise.
Assume that P ̸= NP.
Which of the following statements is true?

Correct Answer: D