2024-161

Dado o grafo abaixo e considerando \(k\) cores, qual das alternativas a seguir exibe uma ordem de eliminação perfeita, anotada com o número de cores livres disponível para cada vértice, no algoritmo guloso para uma coloração própria?

A) 1: \(k\), 2: \(k-1\), 3: \(k-2\), 4: \(k-1\), 5: \(k-2\)

B) 1: \(k\), 2: \(k-1\), 3: \(k-1\), 5: \(k-2\), 4: \(k-3\)

C) 1: \(k\), 2: \(k-1\), 3: \(k-1\), 4: \(k-1\), 5: \(k-3\)

D) 1: \(k\), 2: \(k-1\), 3: \(k-2\), 5: \(k-3\), 4: \(k-4\)

E) N.D.A.

Ideia original de: Artur Silveira