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