Número:
Enunciado: Seja Tn,r um grafo Turán com n vértices e r partições. Qual das implicações abaixo é falsa?
a) Se n < 2r, então Tn,r é color-critical.
b) Se movermos um vértice de uma partição para outra, o grafo deixa de ter o máximo de arestas entre os grafos simples r-partidos.
c) Se incluirmos uma aresta em Tn,r , mantendo-o simples, o número cromático do grafo aumenta.
d) Se r=2, então o grafo é livre de triângulos.
e) NDA
Não está claro para mim o que significa "mover um vértice de uma partição para outra". O conjunto de arestas incidentes a este vértice é modificado para que a partição que recebe o vértice continue sendo um conjunto independente? Como fica isto? Prefiro descartar.
ResponderExcluir