Seja G um grafo simples.
Designaremos por k(G)
o maior inteiro n
tal que o grafo completo Kn
é isomorfo a um subgrafo de G.
O número cromático do grafo
G
será aqui denotado por ¢(G).
Seja Gn o grafo parcial de
Kn que se obtem removendo
três arestas unindo três vértices (i.e. um triângulo).
Supondo que n > 3,
qual das seguintes alternativas está correcta?