MO405 - Questão para a prova oral

Número:

Enunciado: Assinale a alternativa incorreta em relação ao limite superior de coloração.

a) χ(G) ≤ Δ(G) + 1, pela coloração gulosa.


b) χ(G) ≤ 1 + max_i min{d_i, i - 1}, em que d_1 ≥ d_2 ≥ ... ≥ d_n é a sequencia de graus de G. 


c) χ(G) ≤ Δ(G), se o grafo é completo.


d) χ(G) ≤ 1 + max_{H ⊆ G} δ(H), sendo H subgrafo k-crítico de G.


e) NDA


Ideia original de: Rafael de Oliveira Werneck