O algoritmo sequencial para coloração de grafos é capaz de obter boas soluções, apesar de não oferecer a garantia de encontrar o menor número de cores possível para se cobrir um grafo. No entanto, algumas modificações no algoritmo podem fazer com que ele alcance resultados ainda melhores.

Considere o grafo a seguir:

Suponha que uma coloração inicial tenha sido proposta para ele, como apresentado a seguir:

Nessa coloração, os três primeiros vértices receberam a cor 1, os vértices v₄ a v₇ receberam a cor 2 e os demais vértices a cor 3.

Considere o seguinte algoritmo sequencial de coloração de grafos modificado:

Entrada: um grafo G com uma lista de vértices v₁, v₂, …, v_p e um número K de cores utilizadas na coloração prévia do grafo.

Saída: uma coloração f: V(G) → { 1, 2, … } dos vértices de G

01. para cadai ∈{ 1, 2, …, p }

02. se f(v_i) tem cor igual a algum adjacente vj com j < i então

03. f(v_i) ← o próximo número cor que não tenha sido usado em algum vizinho de vi e que respeite o valor limite K.

04. fim se

05. fim para

06. Retornar a coloração de vértices f

Assinale a alternativa que indica uma proposição verdadeira a respeito da aplicação do algoritmo de coloração de grafos modificado sobre o grafo previamente colorido apresentado.

A. A coloração de vértices obtida é a mesma que a obtida pela execução do algoritmo original.

B. O algoritmo causará alteração de cor de todos os vértices coloridos previamente com a cor 2.

C. Os vértices previsamente coloridos com a cor 3 terão suas cores modificadas para outra de maior valor numérico.

D. A classe de cor com maior número de elementos será composta por cinco vértices.

E. Os três primeiros vértices do grafo recebem a mesma sequência de cores em ambos os algoritmos.